# 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.

• Please clarify the question by quoting the passage you don't understand from the paper, URLs do disappear. Jan 7 '17 at 7:03
• If $a$ is a primitive root modulo $q$, then you can't have a small $b$ such that $a^b \equiv 1 \pmod q$. Jan 7 '17 at 9:32

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<a<n$, and choose some $L$. The document suggests some ways to choose $L$. Take the following steps:

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

1.1 If $d_0>1$, we are done.

1.2 Else, continue to 2.

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<d_1<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<n<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.