The Structure and Degrees of Polynomials Computing Square Roots $\mod p$
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912735090966528 |
|---|---|
| author | Chnaras, Foivos Kupinsky, Noah |
| author_facet | Chnaras, Foivos Kupinsky, Noah |
| contents | For an odd prime $p$, we say a polynomial $f\in \mathbb F_p[X]$ computes square roots if $f(a)^2=a$ for all nonzero, perfect squares $a\in \mathbb F_p$. When $p\equiv 3 \mod 4$, it is easy to see that $f(X)=X^{\frac{p+1}{4}}$ is the smallest such polynomial. For $p\equiv 1 \mod 4$, the situation is less clear. Tonelli-Shanks offers an algorithm for constructing polynomials that compute square roots, but the question of whether their degree is minimal remains. In this paper, we study the various degrees and structures of polynomials computing square roots. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22881 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Structure and Degrees of Polynomials Computing Square Roots $\mod p$ Chnaras, Foivos Kupinsky, Noah Number Theory For an odd prime $p$, we say a polynomial $f\in \mathbb F_p[X]$ computes square roots if $f(a)^2=a$ for all nonzero, perfect squares $a\in \mathbb F_p$. When $p\equiv 3 \mod 4$, it is easy to see that $f(X)=X^{\frac{p+1}{4}}$ is the smallest such polynomial. For $p\equiv 1 \mod 4$, the situation is less clear. Tonelli-Shanks offers an algorithm for constructing polynomials that compute square roots, but the question of whether their degree is minimal remains. In this paper, we study the various degrees and structures of polynomials computing square roots. |
| title | The Structure and Degrees of Polynomials Computing Square Roots $\mod p$ |
| topic | Number Theory |
| url | https://arxiv.org/abs/2511.22881 |