Q:

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?

A:

Yes, in Pollard's $p-1$ we can use almost any $a$ in $\gcd(a^{B!}-1,n)$.
Yes, there can be a small advantage in initializing the question's algorithm with $a=2$ because it is computationally cheaper to compute powers of $2$, but that is essentially not used in the proposed pseudo-code.
The rest of this answer explains how that could be. I won't touch the question of choosing the bound $B$, since when we are at optimizing Pollard's $p-1$ we actually need to consider and optimize the choice of two bounds $B_1$ and $B_2$, and compute $\gcd(a-1,n)$ more often than shown, and make a few other changes; that's easily the subject of a PhD.

When computing $x\gets a^k\bmod n$ for $k>0$, the left-to-right binary exponentiation method goes:

$x\gets a$
for each bit in $k$ from second most significant to least significant

if the current bit in $k$ is $0$ then

$x \gets x\times x\bmod n$

else

$x \gets x\times x\times a\bmod n$

When we specialize to $a=2$ and consider large $k$, we can improve the above algorithm. Let $|n|$ be the number of bits in $n$, that is $|n|\underset{\text{def}}=\left\lceil\log_2(n+1)\right\rceil$. We can replace the first $u\approx2\,|n|$ iterations in the algorithm by changing the first step to $x$ to $x\gets (1\ll u)\bmod n$. And, independently, we can replace the last step by $x\gets((x\times x)\ll1)\bmod n$.
Problem is, the way the question's algorithm 9.5 is stated, it only uses $a=2$ for the very first step. Thus in order to get any saving by the method above, we need to change the algorithm slightly. The idea is to choose a bound $B_0\le B$ such that $k=B_0!$ is manageably large, and in the question's algorithm replace the initialization steps for $a$ and $e$ by: $a\gets 2^k\bmod n$ computed by our improved modular exponentiation algorithm, and $e\gets B_0+1$.
That only gives a moderate time saving, and the law of diminishing returns strikes as $B_0$ grows.

