Suppose a,b,c are the cubic roots of:
x^3=1 mod p
where p is prime. One of the roots is obviously 1. Let a=1 then I'm wondering that:
b^2=c mod p
and
c^2=b mod p
and
a+b+c=p
and
b+c=p-1
I'm trying to understand if there is a polinomial algorithm (when p is known) to find b and c.
Regards Massimo.
On
You can find those cubic roots of unity either by following the non-deterministic algorithm of calculating $z=a^{(p-1)/3}$ modulo $p$ for a range of random numbers $a>1$. Unless $a$ is a cubic residue then $z$ will be a solution of $z^2+z+1\equiv 0\pmod p$. Observe that using square-and-multiply the calculation of $a^{(p-1)/3}$ for a fixed $a$ can be done in polynomial time (polynomial in $\log_2p$). Alternatively you can look for an algorithm to calculate $\sqrt{-3}$ modulo $p$, and then apply the quadratic formula. Sorry I can't point you right away at an efficient method for doing that. May be the links here help?
Adding hopefully illuminating examples of the techniques. For the purposes of illustration let's do the case $p=103$. Then $3\mid p-1$ guaranteeing the existence of third roots of unity modulo $p$. We also have $p\equiv3\pmod4$ implying that $-1$ is not a quadratic residue. This will simplify my other demonstration.
Let's first run the (non-deterministic) method of calculating powers $2^{(p-1)/3}$. Here $(p-1)/3=34$. It is our lucky day, and it turns out that the smallest choice $a=2$ will work. All the calculations below are modulo $103$: $$ \begin{aligned} 2^2&=&&\equiv4,\\ 2^4&=(2^2)^2&=4^2&\equiv16,\\ 2^8&=(2^4)^2\equiv16^2&\equiv256&\equiv50,\\ 2^{16}&=(2^8)^2\equiv50^2&=2500&\equiv28,\\ 2^{32}&=(2^{16})^2\equiv28^2&=784&\equiv63,\\ 2^{34}&=2^{32}\cdot2^2\equiv63\cdot4&=252&\equiv46. \end{aligned} $$ Because the result $\neq1$ we can conclude that $b=46$ is a cubic root of unity. Joffan explained that the other must be $c=103-1-b=56$. We can check your claim easily: $$ b^2=46^2=2116\equiv 2116-20\cdot103=56=c. $$
The other method I show needs $p\equiv3\pmod4$ (in addition to $p\equiv1\pmod6$). I want to find a solution of the congruence $$x^2\equiv-3.\qquad(*)$$ Because the solutions of $b^2+b+1\equiv0$ are $b=(-1\pm\sqrt{-3})/2$ and we know that those solutions exist, we also know that $(*)$ has two non-congruent solutions. We could just observe that in this case $10^2\equiv-3$, but that would be cheating, so let's not use that. A key ingredient is that $-1$ is a quadratic non-residue modulo $p$. As the two solutions of $(*)$ are negatives of each other, this means that exactly one of those solutions is a quadratic residue modulo $p$. But the quadratic residues are exactly the zeros of the polynomial $x^{(p-1)/2}-1$. Here $(p-1)/2=51$, so to find the solution $d$ of $(*)$ that is also a quadratic residue, all we need to do is to calculate the gcd of the polynomials $f(x)=x^2+3$ and $g(x)=x^{51}-1$. That gcd must then be a constant multiple of $(x-d)$! The Euclidean algorithm will do that actually very quickly. The only time consuming part is to calculate the remainder of $x^{51}-1$ modulo $x^2+3$. That is no worse than a single run of square-and-multiply. This is because $$ x^2\equiv-3\pmod{f(x)}, $$ so $$ x^{50}=(x^2)^{25}\equiv(-3)^{25}\pmod{f(x)}. $$ A square and multiply shows that $(-3)^{25}\equiv-31\pmod{103}$. Therefore $$ g(x)=x^{51}-1=x(x^{50})-1\equiv-31x-1\pmod{f(x)}. $$ We knew in advance that $\gcd(f(x),g(x))$ is linear, so it has to be a constant multiple of $31x+1$. A run of extended Euclidean algorithm (hopefully you are familiar with that) gives that the modular inverse of $31$ is $10$. We can easily check this: $10\cdot31=310\equiv310-3\cdot103=1$.
Therefore the monic gcd is $$ \gcd(x^2+3,x^{51}-1)=x+10. $$ This has the obvious zero $d=-10$, which can then serve in the role of $\sqrt{-3}$ modulo $103$. Therefore the solutions of $b^2+b+1=0$ are $$ b=\frac{-1\pm\sqrt{-3}}2=\frac{-1\pm(-10)}2= \begin{cases}-11/2\equiv (103-11)/2=46&,\text{and}\\ 9/2\equiv(103+9)/2=56.\end{cases} $$
There may be something better out there, but when these algorithms apply, they have polynomial complexity.
With $p$ prime and $p\equiv 1 \bmod 3$, you will have three cubic roots of $1$, $\{1,b,c\}$, taking $1<b,c<p$. The first non-unity root determines the other one since we know $b^2\not\equiv 1$ and $(b^2)^3\equiv (b^3)^2 \equiv 1^2\equiv 1 \bmod p$, so $c\equiv b^2$.
Also of course $c^2\equiv b^4\equiv b^3\cdot b\equiv b\bmod p$.
Then given that $b\ne 1$ we know that $b{-}1$ is coprime to $p$ and so $(b-1)(1+b+b^2) = b^3-1 \equiv 0 \bmod p$ implies $(1+b+b^2) \equiv 0 \bmod p$. Then given that $1+b+c<2p$ we must have $1+b+c=p$.
You would need to define what you mean by a polynomial algorithm to get any useful answer there.