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&gt;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 $&lt;B$ 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;


  
  select a smoothness bound B
  define $M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }$
  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)
  compute $g = \gcd(a^M − 1, n)$ (note: exponentiation can be done modulo $n$)
  if $1 &lt; g &lt; n$ then return $g$
  if $g = 1$ then select a larger $B$ and go to step 2 or return failure
  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.