Role of primitive roots in Pollard's P-1 factorization algorithm I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states...


  For example, note that 2^8 = 256 ≡ 1 mod 17 even though 2 is relatively prime to 17 and 8 ≠ 0.
  The point here is that this cannot happen if a is a primitive root modulo q. But a sizeable number of integers are primitive roots
  modulo q, and even if a is not a primitive root it’s not guaranteed that we necessarily have to run into this situation, so choosing a
  different a should work. 


However I am a little confused and don't get exactly what it's saying. Can someone explain the role of primitive roots in Pollard's P-1 factorization.
I will follow the steps in the document, emphasizing where the primitive root comes in.

Let $n$ be a product of two primes, say $p$ and $q$, pick $1&lt;a&lt;n$, and choose some $L$. The document suggests some ways to choose $L$. Take the following steps:


Compute $d_0=\gcd(a,n)$.

1.1 If $d_0&gt;1$, we are done.     

1.2 Else, continue to 2.
Compute $d_1=\gcd(a^L-1,n)$.

2.1 If $d_1=1$, then $p\not\mid a^L-1$, i.e. $a^L\not\equiv1\pmod{p}$. Choose a new $L$ and repeat. 

2.2 If $1&lt;d_1&lt;n$, we are done.

2.3 If $d_1=n$, choose a new $a$ and repeat.


The goal is to end up in situation 2.2, so we can wonder when we do not.  

Instead, we could end up in 2.1. This happens when $a^L\not\equiv1\pmod{p}$, thus when $p-1\not\mid L$. As the document states, we actually want $p-1\mid L$. This is clearly a condition on $L$, independent of $a$, so we can simply choose a new $L$ and restart.

Finally, we could end up in situation 2.3. As explained, this happens when $$a^k\equiv 1\pmod{q}$$
where $k=L\pmod{q-1}$. For which $a$'s can this happen? Well, if $k=0$, then it happens for all of them. In this case we have been quite unlucky, and choosing a new $a$ has only a very small probability of being helpful. 

If $k\neq 0$, then this can not happen for all $a$'s. Remember that a primitive root $x$ modulo $q$ is defined as a non-zero integer $x$ such that $x^n\neq1\pmod{q}$ for all $0&lt;n&lt;q-1$. In other words, $a^k\equiv1\pmod{q}$ can only happen if $a$ is not a primitive root modulo $q$. We can choose a new $a$, and hope that the new one is a primitive root.