On the degree of polynomials computing square roots mod $p$

Suppose $f(X)$ is of degree $d<\frac{p-1}{3}$ and computes square roots in $\mathbb{F}_{p}$. Then, since $X^{(p-1)/2}-1$ is the vanishing polynomial of the set of nonzero perfect squares in $\mathbb{F}_{p}$, we have:

Let $A(X)$ be the polynomial of degree $2d-(p-1)/2$ such that

Let $B(X)=X-A(X)$. Then we get:

where:

• •

  $\deg(f(X))=d$.

• •

  $\deg(A(X)),\deg(B(X))\leq 2d-(p-1)/2$.

• •

  $A(X)\neq 0$. If $A(X)=0$ then $f(X)^{2}=X$, which is impossible for a polynomial $f(X)$.

• •

  $B(X)\neq 0$. Otherwise $A(X)=X$, and $f(X)^{2}=X^{(p+1)/2}$, which is possible only if $p\equiv 3\mod 4$.

These conditions together will give us our lower bound on $d$.

Taking derivatives²²2Throughout this paper, we work with formal derivatives of polynomials. of both sides of (1), we get:

Computing $2f(X)^{2}f^{\prime}(X)$ in two ways using (1) and (2), we get:

Now, using our assumption on $d$, the degrees of $2f^{\prime}(X)B(X)$ and $f(X)B^{\prime}(X)$ are both at most $3d-(p-1)/2-1<(p-3)/2$, and thus taking the above equation mod $X^{(p-3)/2}$,

Since $B(X)\neq 0$, we get $\frac{2f^{\prime}(X)}{f(X)}=\frac{B^{\prime}(X)}{B(X)}$. Since $2\deg(f),\deg(B)<p$, by a basic property of logarithmic derivatives, this implies $f(X)^{2}=\lambda B(X)$ for some nonzero $\lambda$, contradicting the fact that $A(X)\neq 0$. (See Remark 1 in Section 2.2 for a precise statement and a proof.)

Thus our assumption that $d<\frac{p-1}{3}$ is wrong, and the theorem follows. ∎

We use the idea of the Berlekamp-Welch Reed-Solomon decoding algorithm [WB83].

Let $U\subseteq S$ be the set of $a\in S$ where $f(a)^{2}\neq a$.

Let $E(X)\in\mathbb{F}_{p}[X]$ be the vanishing polynomial of $U$, given by:

Note that $E$ is a nonzero polynomial of degree at most $e$.

Then we have:

Let $A(X)$ be the polynomial of degree at most $2(e+d)-(p-1)/2$ such that:

Let $g(X)=E(X)\cdot f(X)$, and $B(X)=E(X)^{2}\cdot X-A(X)$.

Then

We have:

• •

  $\deg(g)\leq d+e$,

• •

  $\deg(B)\leq\max(2e+1,2(e+d)-(p-1)/2)$.

• •

  $A(X)\neq 0$. Otherwise $E(X)^{2}\cdot f(X)^{2}=E(X)^{2}\cdot X\Longrightarrow f(X)^{2}=X$, which is impossible.

• •

  $B(X)\neq 0$. Otherwise $E(X)^{2}\cdot X=A(X)$, and so $E(X)^{2}f(X)^{2}=E(X)^{2}X^{(p+1)/2}$, which implies that $f(X)^{2}=X^{(p+1)/2}$. This is only possible if $p\equiv 3\mod 4$.

Plugging this into Lemma 2.1, we get:

• •

  $$(d+e)+\left(2(d+e)-\frac{p-1}{2}\right)\geq\frac{p-1}{2},$$

  if $2d-(p-1)/2\geq 1$,

• •

  $$(d+e)+(2e+1)\geq\frac{p-1}{2},$$

  if $2d-(p-1)/2\leq 0$.

This tells us that either:

or:

and thus:

which gives us the desired claim. ∎

Since $p\equiv 1\mod 4$, we get that $-1$ is a perfect square mod $p$. Let $i\in\mathbb{F}_{p}$ be one of the square roots of $-1$. Our main ingredient is the Tonelli-Shanks algorithm [Sha73, Ton91] computing square roots mod $p$. For $p=4\ell+1$, the algorithm essentially gives a formula for the square root depending on two cases. Specifically, let $u:S\to\mathbb{F}_{p}$ given by:

Then for all $a\in\mathbb{F}_{p}$, $u(a)$ is a square root of $a$.

This is already quite special; the set $S$ is partitioned into two equal sized parts $S_{0}$ and $S_{1}$, and on each $S_{i}$ we have a polynomial $f_{i}(X)$ computing the square root of degree about $\frac{1}{2}|S_{i}|$. (This is the lowest possible degree, since $f_{i}(X)^{2}-X$ is a nonzero polynomial that vanishes on all of $S_{i}$.)

Usually if we have this kind of setup, even though the $f_{i}$ have unusually low degree, the unique polynomial $f$ (obtained from the Chinese remainder theorem) which restricts to $f_{i}$ on $S_{i}$ has no reason to have unusually low degree. But in this case it does!

Using the usual Chinese remainder formula, we consider the polynomial $f(X)\in\mathbb{F}_{p}[X]$ given by:

By design, we have $f(a)=u(a)$ for all $a\in S$. Finally, notice that $\deg(f)\leq\frac{3p+1}{8}$.

As a sanity check, we directly verify that $f(X)^{2}\equiv X\mod(X^{(p-1)/2}-1)$. Indeed,

as desired. ∎

Let $m=(p-1)/2$. Let $S\subseteq\mathbb{F}_{p}$ be the set of nonzero perfect squares, and note that $|S|=m$. For each $\alpha\in S$, let $\delta_{\alpha}(X)\in\mathbb{F}_{p}[X]$ be the unique polynomial of degree $\leq(m-1)$ such that for all $\beta\in S$:

Explicitly, we have:

Then given a function $u:S\to\mathbb{F}_{p}$, the unique polynomial $f(X)\in\mathbb{F}_{p}[X]$ of degree at most $m-1$ such that $f(\alpha)=u(\alpha)$ for all $\alpha\in S$ is given by:

Our goal is to pick $u$ where each $u(\alpha)$ is one of the two square roots of $\alpha$ so that many of the leading coefficients of $f(X)$ equal $0$.

We now use the structure of $S$. Let $g$ be a generator of $\mathbb{F}_{p}^{*}$. Then $S=\{g^{2j}\mid 0\leq j<(p-1)/2\}$. Furthermore, for $\alpha=g^{2j}\in S$, one of the two square roots of $\alpha$ is $g^{j}$.

Thus, our problem can be reformulated as choosing a function $v:S\to\{\pm 1\}$ such that:

has many leading coefficients equal to $0$.

Observe that the coefficient of $X^{m-i}$ in $f(X)$ equals:

Thus, to get a polynomial $f(X)$ of degree $<m-t$, we want to find a vector $v\in\{\pm 1\}^{m}$ that lies in the kernel of the Vandermonde-type matrix $M\in\mathbb{F}_{p}^{t\times m}$, where:

(The row index $i$ runs from $1$ to $t$, the column index $j$ runs from $0$ to $m-1$.)

For later use, for a vector $y\in\mathbb{F}_{p}^{t}$, we define $P_{y}(Z)\in\mathbb{F}_{p}[Z]$ to be the polynomial:

Thus for $j\in\{0,1,\ldots,m-1\}$, the $j$th entry of $M^{T}y$ equals $P_{y}(g^{j})$.

To show that there exists the desired $\pm 1$ vector, we count the number of such vectors using Fourier analysis. Let $\omega$ be a $p$th root of unity in $\mathbb{C}$. The number of such $\pm 1$ vectors equals:

For $y=0$, the expression inside the expectation equals $2^{m}$. We will show that for the remaining $p^{t}-1$ values of $y$, the expression inside the expectation is very small.

Fix any $y\neq 0$. The expression inside the expectation equals: