5
$\begingroup$

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)?

$\endgroup$
  • 3
    $\begingroup$ Is there some reason you expect it is possible to express $r$ in terms of $c$ without using cube roots? $\endgroup$ – Eric Wofsey Jan 27 at 21:13
  • $\begingroup$ Should $p$ satisfy one of the congruences, or both? I'm guessing both, but it is slightly ambiguous. $\endgroup$ – Inactive - Objecting Extremism Jan 27 at 21:13
  • $\begingroup$ @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? $\endgroup$ – Inactive - Objecting Extremism Jan 27 at 21:19
  • $\begingroup$ $p$ should satisfy the both congruences. Yes, I want rational functions in $c$ if this is possible. $\endgroup$ – Dima Koshelev Jan 27 at 21:58
  • 1
    $\begingroup$ 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 $\endgroup$ – lonza leggiera Jan 27 at 22:03
1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Feb 1 at 6:20

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.