1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.