# #StackBounty: #prime-numbers #factoring #number-theory #pki Pollard's p – 1 – how do you set the bound & how do you set the bas…

### Bounty: 50

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.

1. 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.
2. 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

1. 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?
2. In both the methods, how do choose the $$a$$‘s?
3. 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)?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.