# For $c\in\mathbb{F}_p^*$, the cubic $t^3-3ct^2-3t+c$ has exactly one root $r\in\mathbb{F}_p$. Express $r$ in terms of $c$ without cubic roots.

For some $$c \in \mathbb{F}_p^*$$ consider the polynomial $$f(t) = t^3 - 3ct^2 - 3t + c$$ for $$p \equiv 1$$ (mod $$3$$) and $$p \equiv 3$$ (mod $$4$$). In this case $$3$$ is a quadratic non-residue modulo $$p$$ and hence the discriminant $$\Delta = 2^23^3(c^2+1)^2$$ of $$f$$ is also a quadratic non-residue modulo $$p$$.

Thus $$f$$ has exactly one root $$r \in \mathbb{F}_p$$. For $$c=1$$ the root $$r = -1$$. How explicitly express $$r$$ through $$c$$ in general case without usage of the Cardano formula (i.e., without cubic roots)?

• Is there some reason you expect it is possible to express $r$ in terms of $c$ without using cube roots? – Eric Wofsey Jan 27 at 21:13
• Should $p$ satisfy one of the congruences, or both? I'm guessing both, but it is slightly ambiguous. – Inactive - Objecting Extremism Jan 27 at 21:13
• @Eric Wofsey You could use sixth roots, but I'm guessing OP doesn't want any $n$-th roots. Perhaps just a rational function in $c$, or a few of them for a few cases? – Inactive - Objecting Extremism Jan 27 at 21:19
• $p$ should satisfy the both congruences. Yes, I want rational functions in $c$ if this is possible. – Dima Koshelev Jan 27 at 21:58
• I'm not sure this could be described as giving an "explicit" expression for $\ r\$ in terms of $\ c\$, but if I were given $\ c\$ and wanted to find $\ r\$, I'd simply use the Cantor-Zassenhaus algorithm to factorise the polynomial – lonza leggiera Jan 27 at 22:03

It is indeed possible to express the root as a rational function of $$\ c\$$. This follows from the fact that$$^{\mathbf{\dagger}}$$, under the stated conditions, the polynomial $$\ t-r\$$ must be the gcd of the polynomials $$\ f\left(t\right)\$$ and $$\ t^{p-1}-1\$$. In the Euclidean algorithm for computing the gcd, the coefficients of the initial polynomials $$\ t^{p-1}-1\$$ and $$\ f\left(t\right)\$$ are rational functions of $$\ c\$$ (with coefficients in $$\mathbb F_p\$$), and it's easy enough to show that the remainder of a polynomial $$\ \pi_1(t)\in \mathbb F_p[t]\$$ modulo another, $$\ \pi_2(t)\$$, has coefficients that are rational functions of those of $$\ \pi_1(t)\$$ and $$\ \pi_2(t)\$$. From this it follows that the coefficients of the gcd must be rational functions of those of the initial polynomials, and hence of $$\ c\$$.

In practice, the function can be found for any given $$\ p\$$ by treating $$\ c\$$ as an indeterminate, and calculating the gcd in $$\ \mathbb F_p(c)[t]\$$, where $$\ \mathbb F_p(c)\$$ is the field of rational functions in $$\ c\$$ over $$\ \mathbb F_p\$$. Since $$\ c\$$, as an element of $$\ \mathbb F_p^*\$$, is a root of the polynomial $$\ t^{p-1}-1\$$, monomials, $$\ c^q\$$, of degree $$\ p-1\$$ or higher can nevertheless be replaced by $$\ c^{q\,\mathrm{mod}\,(p-1)}\$$ as the calculation proceeds. The denominator of the rational function obtained by this procedure cannot have a linear factor other than $$\ c\$$, since if it did, being $$\ c-\rho\$$, say, with $$\ \rho \ne 0\$$, then the degree of $$\ \gcd\left( t^{p-1} - 1, t^3 - 3\rho t^2 - 3t^2 + \rho\right)\$$ would have to be zero.

Here are the expressions for $$\ r\$$ for the cases $$\ p=7,19\$$ and $$\ 31\$$, respectively:

$$\frac{3}{5c^5+5c^3+c}\\ \ \\ \frac{\small 4c^{14}+3c^{12}+10c^{10}+12c^8+14c^6+4c^4+8c^2+7}{\small 17c^{17}+17c^{15}+18c^{13}+4c^{11}+2c^9+11c^7+17c^5+13c^3+10c}\\ \ \\ \frac{\tiny 15c^{26}+5c^{24}+5c^{22}+16c^{20}+21c^{18}+2c^{16 }+29c^{14}+29c^{12}+24c^{10}+20c^8+5c^6+14c^4+14c^2+11}{\tiny 29c^{29}+29c^{27}+17c^{25}+5c^{23}+18c^{21}+17c^{19}+2c^{17}+25c^{15}+12c^{13}+9c^{11}+12c^7+3c^5+12c^3+3c}$$

The pattern observable here in the leading terms of the numerators and denominators continues through the primes $$\ 43\$$ and $$\ 67\$$, the first term of the numerator being $$\ (p-4)\,c^{p-5}\$$ in all cases except $$\ p=7\$$, and the first two terms of the denominator being $$\ (p-2)\,c^{p-2} + (p-2)\,c^{p-4}\$$ in all cases.

The softwear package I used to perform the gcd calculations crashed when I tried $$\ p=79\$$, so I haven't looked at any primes beyond $$\ 67\$$.

$$\mathbf\dagger$$ Or even from from the simple fact that it's a function of $$\ c\$$, as Eric Wofsey points out in the comments below.

Update: As Eric Wofsey observes in the comment below, the root can also be expressed as a polynomial function of $$\ c\$$. If we let $$\ c_r = \frac{r^3-3\,r}{3\,r^2-1}\ \mathrm{mod}\ p\$$, the value of $$\ c\$$ corresponding to the root $$\ r\$$, one well-known expression for such a polynomial is: $$\sum_{r\in {\mathbb F}_p^*} r \prod_{u\in{\mathbb F}_p^*\setminus\{c_r\}} \frac{c-u}{r-u}\ .$$ For $$\ p=7,19\$$ and $$\ 31\$$ the polynomials are: $$5\,c^5 + 4\,c^3 + 4\,c \\ \ \\ 8\,c^{17}+6\,c^{13}+4\,c^{11}+2\,{c^9}+7\,c^7+16\,c^5+5\,c^3+8\,c\\ \ \\ {\tiny 3c^{29}+22c^{27}+5c^{25}+12c^{23}+12c^{21}+15c^{19}+27c^{17}+5c^{15}+16c^{11}+14c^9+3c^7+22c^5+17c^3+12c}$$

• Every function $\mathbb{F}_p\to\mathbb{F}_p$ can be written as a rational function (even a polynomial), so this doesn't really say anything. I guess the specific algorithm you describe might be useful though. – Eric Wofsey Feb 1 at 6:20