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"]
]