# Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor n = 3317

$$r_2 \equiv 2^2 \equiv 4\ \text{(mod 3317)}\\ r_3 \equiv 4^3 \equiv 64\ \text{(mod 3317)}\\ r_4 \equiv 64^4 \equiv 3147\ \text{(mod 3317)}\\ r_5 \equiv 3147^5 \equiv ...\ \text{(mod 3317)}$$

The value of $r_5$ was supposed to be calculated easily by using math tools on computer (e.g. UNIX tool bc or Pari/GP), but if I have to solve this question during an exam, any feasible way other than harshly calculating them by hand?

I am allowed to use scientific calculator (My model is CASIO fx-82), but calculating $3147^5$ on the calculator seemed still unfeasible.

Any better solution to this question? Thanks a lot.

## 1 Answer

Noting that $3147= -170 \bmod 3317$ may help.

When doing calculations by hand or calculator, it is often useful to considered remainders with least absolute value. This is just the observation that $r \equiv m-r \bmod m$.

Another observation is that you don't need to compute $3147^5 \bmod 3317$ by first computing $3147^5$ and then reducing it mod $3317$. You can reduce after every multiplication step or use a binary exponentiation method based on squaring: $3147^5 = (3147^2)^2\cdot 3147$.

• Thank you for your solution, but can I still use $(-170)^5$ = $(-170^2)^2 \cdot -170$? – Yang Xia Jun 9 '14 at 13:30
• @YangXia, sure. – lhf Jun 9 '14 at 13:31