11
$\begingroup$

How can I find solution for $x^3 \equiv 1 \pmod p$ ($p$ a prime) efficiently?

Trivial root is $x_1 = 1$. I need to find other roots $x_2, x_3$.

3 Answers 3

10

The integers modulo $p$ form a field. Since $x^3 - 1 = (x-1)(x^2+x+1)$, the problem is equivalent to solving $x^2+x+1\equiv 0 \pmod{p}$. For $p\neq 2$, the usual quadratic formula works; so you would need to find $y$ such that $y^2\equiv -3\pmod{p}$. If $p=2$, then $x^2+x+1=0$ has no solutions, and if $p=3$, then $x^3-1 = (x-1)^3$, so again there is no root other than $x=1$.

Let's consider the other primes, $p\gt 3$.

Using quadratic reciprocity, if $p\equiv 1\pmod{4}$, then $-1$ is a square modulo $p$ and we have: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right).$$ So if $p\equiv 1 \pmod{3}$ (hence $p\equiv 1 \pmod{12}$) then $-3$ is a square modulo $p$; if $p\equiv 2\pmod{3}$ (so $p\equiv 5\pmod{12}$), then $-3$ is not a square modulo $p$, so there is no other solution.

If $p\equiv 3\pmod{4}$, then $-1$ is not a square modulo $p$, and we have: $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)$$ (since $\left(\frac{3}{p}\right) = -\left(\frac{p}{3}\right)$); again, if $p\equiv 1\pmod{3}$ (so $p\equiv 7\pmod{12}$) then $-3$ is a square modulo $p$; and if $p\equiv 2\pmod{3}$ (so $p\equiv 11\pmod{12}$) then $-3$ is not a square modulo $p$.

In summary, there are roots of $x^3-1$ modulo $p$ other than $x\equiv 1\pmod{p}$ if and only if $p\equiv 1\pmod{6}$. If $p=6k+1$ is such a prime, then the two roots of $x^3-1$ other than $x=1$ are precisely the roots of $x^2+x+1$, which are $$\frac{-1\pm\sqrt{-3}}{2} = -3k(-1\pm a),$$ where $a$ is an integer such that $a^2\equiv -3\pmod{p}$. This means you still need to figure out the square root, which can be done using any of the methods suggested by Bill Dubuque, such as Tonelli's algorithm (say, in Shanks' version as described in Wikipedia).

Added: As Alex Bartel notes in comments and in his own answer, one can avoid the use of quadratic reciprocity above. Since the units of $\mathbb{Z}/p\mathbb{Z}$ form a cyclic group of order $p-1$, there are nontrivial solutions to $x^3=1$ if and only if $3$ divides the order, that is, if and only if $p\equiv 1\pmod{3}$. From there, it is an easy jump to solutions if and only if $p\equiv 1 \pmod{6}$, since otherwise we would have $p\equiv 4\pmod{6}$ which is impossible since $p$ is prime. Once one establishes that, the quadratic formula can be applied safe in the knowledge that these primes must have $-3$ as a quadratic residue.

  • 1
    Your method for showing that there are other roots if and only if $p\equiv 1\pmod{6}$ is more complicated than necessary. Just observe that $\mathbb{F}_p^\times$ is cyclic of order $p-1$.2010-12-29
  • 0
    The general case is quite simple (in fact no more difficult than what you wrote above) e.g. see the single-page exposition in Bach & Shallit referenced in my post.2010-12-29
6

First, note that if $p \equiv 2\text{ mod } 3$, then raising to the third power is a bijection on $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, so that 1 is the only root. If $p \equiv 1\text{ mod } 3$, then the only way I can think of to find the roots is to find a primitive root modulo $p$ (i.e. a generator of the cyclic group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$) and take it to the powers $(p-1)/3$ and $2(p-1)/3$.

  • 0
    Assuming GRH, a linear scan is probably good enough to find primitive roots: [Order of Magnitude of Primitive Roots](http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Order_of_magnitude_of_primitive_roots).2010-12-28
  • 0
    There is also this MO question and the references therein, as far as finding primitive roots is concerned: http://mathoverflow.net/questions/8345/reference-of-primitive-root-mod-p2010-12-28
  • 4
    No reason to actually find a primitive root. Just guess $g$ and compute $g^{(p-1)/3}$. If you don't get $1$. you have won. If not, guess another $g$. The probability of success is $2/3$ so you won't have to guess very many possibilities.2010-12-28
  • 0
    Note: There is a theoretical issue if your random number generator loves to produces cubes modulo $p$. The theoretical question of how to avoid this is an interesting one; in practice, I don't think any existing random number generator is believed to have this problem.2010-12-28
5

Tonelli's algorithm for square-roots can easily be generalized to compute d'th roots in finite fields, e.g. see Adleman; Manders; Miller: On taking roots in finite fields, and Bach; Shallit: Algorithmic number theory, section 7.3.