In Pollard’s p-1 algorithm for factoring N, you try to find a L such that p – 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors.
I have seen 2 methods to do this.
- For n from 1 to Bound, try $L = n!$ (i.e. factorial(n)) & try the $gcd(pow(a,L,N)- 1, N)$ for each one.
- for n from 1 to Bound, try $L = LCM(range(1,n))$ & try the $gcd(pow(a,L,N)- 1, N)$ for each one.
In either method, once you hit the Bound unsuccessfully without finding a factor, you redo the loop with a new $a$
I have a few questions
- How do you choose the Bound for each of the 2 methods? You are trying to check if the factor is Bound-Powersmooth, but how do you arrive at what Bound you want to check – i.e. what powersmoothness you expect?
- In both the methods, how do choose the $a$‘s?
- In both the methods, how many such $a$‘s do you try before giving up (because p – 1 probably doesn’t have any small factors)?