# Purpose of using a=2 in Pollard p-1 factorization method

The Pollard p-1 factorization method states if $$\gcd(2^{B!}-1,n)=p$$ where $$p>1$$ and $$B$$ bounds the prime factors of $$p$$, then $$p$$ is a prime factor of $$n$$.

• Shouldn't it be $$\gcd(a^{B!}-1,n)$$ for any arbitrary $$a$$?
• Why are we choosing $$a=2$$? Is it because it is computationally cheaper to compute powers of $$2$$? ( left shift ).
• Moreover, should $$B$$ be an upper bound of the prime factor of $$p-1$$ or an upper bound of the prime factor of $$p-1$$ along with its powers?

• Shouldn't it be $$\gcd(a^{B!}-1,n)$$ for any arbitrary $$a$$.

Yes, and your code tries calculates it in the while loop. Note: normally

$$M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$$ only primes which are less then or equal to $$B$$ constitute to $$M$$. The pseudocode in your slide includes all numbers $$ which is not correct, it must be prime less or equal to $$B$$.

• Why are we choosing $$a=2$$? is it because it is computationally cheaper to compute powers of $$2$$? ( left shift ).

We want a random integer $$a$$ that is co-prime to $$n$$, i.e $$\gcd(a,n)=1$$. If 2 is possible choice as in RSA modulus - $$n$$ is a product of two odd primes, it will be easy to calculate $$\gcd(2^{B!}-1,n)$$

• moreover, should $$B$$, be an upper bound of prime factor of $$p-1$$ or upper bound of prime factor of $$p-1$$ along with its powers?

$$B$$ is a smooth number, and in the beginning, you select any smoothness bound for $$B$$. From Wikipedia code;

1. select a smoothness bound B
2. define $$M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$$
3. randomly pick a coprime to $$n$$ (note: we can actually fix $$a$$, e.g. if $$n$$ is odd, then we can always select $$a = 2$$, random selection here is not imperative)
4. compute $$g = \gcd(a^M − 1, n)$$ (note: exponentiation can be done modulo $$n$$)
5. if $$1 < g < n$$ then return $$g$$
6. if $$g = 1$$ then select a larger $$B$$ and go to step 2 or return failure
7. if $$g = n$$ then select a smaller $$B$$ and go to step 2 or return failure

So the algorithm in sense an adaptive algorithm. In a failure either you can stop or adjust the smoothness bound.