# Pollard's p - 1 - how do you set the bound & how do you set the base numbers

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)?

I believe choosing $$a$$ does not matter much, and changing $$a$$ is not useful at all, until you get a non-trivial $$gcd$$. The idea is that for new $$a$$ you have to multiply by all those $$1,2,3,...$$ again, while you've already done this work for previous $$a$$. You might get a new $$a$$ such that some large factor $$d$$ of $$p-1$$ is already removed, and then you need a smaller bound $$L$$ to work, but the chance of that is $$1/d$$ and you rather keep raising your original $$a$$ to next powers and reach power $$d$$ naturally.
The only issue that can occur - is that you will arrive at 1 mod $$p$$ and 1 mod $$q$$ simultaneously (i.e. get $$a^L\equiv 1 \mod{n}$$), which does not leak a factor. Then you try another $$a$$, but at least you learn that Pollard's $$p-1$$ is likely to work well on this number.
• How does one suspect that p-1 is smooth? Is there any algorithm which tells if one of the factors of N may be smooth & also what is the smoothness bound? Jul 12 at 11:44
• As far as $a$ goes, I think it's not guaranteed that every a would work, so if one $a$ fails, you move on to the next one. Or is this not right? Jul 12 at 11:45
• The method is guaranteed to work for any $a$ in the sense that you will arrive at $a^L \equiv 1 \mod p$. However, if you get $a^L \equiv 1 \mod q$ for the same $L$, this does not lead to factorization. This would hint that the p-1 method would indeed work on this N and then trying another $a$ makes sense (or better try the same $a$ with a divisor of $L$ instead). Otherwise, there is no sense in switching $a$ until you get $a^L\equiv 1 \mod p$. Jul 12 at 13:45
• If you get your number from some challenge - no I am trying to understand the algorithm. Jul 12 at 15:04