Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

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.

share|improve this answer
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$. –  Alex B. Dec 29 '10 at 3:26
    
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. –  Bill Dubuque Dec 29 '10 at 17:13
add comment

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

share|improve this answer
    
Assuming GRH, a linear scan is probably good enough to find primitive roots: Order of Magnitude of Primitive Roots. –  Aryabhata Dec 28 '10 at 8:04
    
There is also this MO question and the references therein, as far as finding primitive roots is concerned: mathoverflow.net/questions/8345/… –  Alex B. Dec 28 '10 at 8:25
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. –  David Speyer Dec 28 '10 at 22:22
    
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. –  David Speyer Dec 28 '10 at 22:24
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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