Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SQUARE ROOTS:
Reports tagged with square roots:
TR23-177 | 18th November 2023
Kiran Kedlaya, Swastik Kopparty

On the degree of polynomials computing square roots mod p

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint