1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.