Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.22881 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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.