Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-177 | 23rd January 2024 05:12

On the degree of polynomials computing square roots mod p

RSS-Feed




Revision #1
Authors: Kiran Kedlaya, Swastik Kopparty
Accepted on: 23rd January 2024 05:12
Downloads: 7
Keywords: 


Abstract:

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified $(p-1)/2$ evaluations (up to sign) of the polynomial $f(X)$.
On the other hand, for $p \equiv 1$ mod $4$ there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in $\mathbb F_p$; it could have been anywhere between $\frac{p}{4}$ and $\frac{p}{2}$.

We show that for all $p \equiv 1$ mod $4$, the degree of a polynomial computing square roots has degree at least $p/3$.
Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients.
The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost $p/3$.

In the other direction, a result of Agou, Deligl├ęse, and Nicolas (Designs, Codes, and Cryptography, 2003) shows that for infinitely many $p \equiv 1$ mod $4$, the degree of a polynomial computing square roots can be as small as $3p/8$.



Changes to previous version:

We learnt that our upper bound for special p, Theorem 1.3, had been proved by Agou, Deligl├ęse and Nicolas in 2003. Added some relevant references and did some small fixes.


Paper:

TR23-177 | 18th November 2023 05:20

On the degree of polynomials computing square roots mod p





TR23-177
Authors: Kiran Kedlaya, Swastik Kopparty
Publication: 18th November 2023 05:20
Downloads: 195
Keywords: 


Abstract:

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified $(p-1)/2$ evaluations (up to sign) of the polynomial $f(X)$.
On the other hand, for $p \equiv 1$ mod $4$ there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in $\mathbb F_p$; it could have been anywhere between $\frac{p}{4}$ and $\frac{p}{2}$.

We show that for all $p \equiv 1$ mod $4$, the degree of a polynomial computing square roots has degree at least $p/3$.
Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients.
The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost $p/3$.

In the other direction, we also show that for infinitely many $p \equiv 1$ mod $4$, the degree of a polynomial computing square roots can be $(\frac{1}{2} - \Omega(1))p$.



ISSN 1433-8092 | Imprint