Thread: Cryptography -- Pollard p-1 Algorithm in Mathematica

Hi, I've got a weird problem here. I'm trying to implement the Pollard P-1 algorithm in Mathematica, which my textbook states is guaranteed to work for $\displaystyle B = \sqrt{n}$, but in this particular example, if B gets too large, say, equal to 500, which is about the square root of the number in consideration, the algorithm actually stops working. My instructor and I looked at it for a long time and decided it's correct rendering of Douglas Stinson's pseudo-code from Cryptography: Theory and Practice... so what's going on? I've found it works for B ranging from 14 to 251, but no larger.

n = 262063;
B = 251; (* Largest B that works *)
a = 2;

For[i = 2, i < B, i++,
a = PowerMod[a, i, n];
]

d1 = GCD[a - 1, n];

If[
1 < d1 && d1 < n,
Print["d is " <> ToString[d1] <> " and n/d is " <> ToString[n/d1]],
Print["Fail"]
]

This is because, in the For loop, you extract the two factors, and what is detected as a factor is n.
This is why, in the Pollard method, one must do the divide GCD check often enough.
You may extent the multiplys at least until B=sqrt(n), but you must check, for numbers like yours every 50's or 100's. If you do not find after the first 100, then continue for another 100.
See Hans Riesel book, prime numbers and computer methods for factorization for more details.