### hly1204's blog

By hly1204, history, 4 months ago,

Suppose $p$ is an odd prime and $a$ is a quadratic residue modulo $p$. Cipolla's algorithm shows that $b:=x^{(p+1)/2}\bmod{(x^2-tx+a)}$ such that $b^2=a$ for some irreducible polynomial $x^2-tx+a\in\mathbb{F}_p[x]$.

I don't know how to prove this properly. If there are any mistakes or typos, please let me know, thanks! Let $\alpha$ be a zero of $x^2-tx+a$, $\mathbb{F}_p(\alpha):=\lbrace a_0+a_1\alpha :a_0,a_1\in\mathbb{F}_p\rbrace$, and let $\beta$ be a zero of $x^2-(t^2-4a)$, $\mathbb{F}_p(\beta):=\lbrace a_0+a_1\beta :a_0,a_1\in\mathbb{F}_p\rbrace$. We may easily find homomorphisms between $\mathbb{F}_p(\alpha)$ and $\mathbb{F}_p(\beta)$. So I think we just need to show that $((t+\beta )/2)^{p+1}=a$.

A lot of blogs show that $(t+\beta)^p=t-\beta$ according to binomial theorem and Fermat's little theorem, so

\begin{aligned} ((t+\beta)/2)^{p+1}&=(t+\beta)(t-\beta)/4\\ &=(t^2-\beta^2)/4\\ &=a \end{aligned}

Bostan and Mori's paper shows that the computation of $x^n$ modulo a monic polynomial sometimes is equivalent to the computation of one term of a rational function $P(x)/Q(x)$ where $P,Q$ are both polynomials and $\deg(P(x))\lt \deg(Q(x))$.

We have

$b=\left[x^{(p+1)/2}\right]\dfrac{1-tx}{1-tx+ax^2}$

and

$\left[x^n\right]\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}= \begin{cases} \left[x^{(n-1)/2}\right]\dfrac{k_1-k_0k_2+k_1k_3x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{if }n\bmod 2=1\\ \left[x^{n/2}\right]\dfrac{k_0+(k_0k_3-k_1k_2)x}{1+(2k_3-k_2^2)x+k_3^2x^2}&\text{otherwise} \end{cases}$

This may save some multiplications.

submission(Library Checker)

Actually, the initial value of $k_1$ does no matter to the result. So we could mainly focus on the computation of one term of the inverse of formal power series. I don't know if we could do better.

• +112

 » 4 months ago, # |   0 Auto comment: topic has been updated by hly1204 (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 3 →   +41 Berlekamp-Rabin algorithm looks simpler, easier to implement and faster to me. Also it's easily generalized to finding roots of higher order and even roots of arbitrary polynomials over $\mathbb Z_p$.Problem. For prime $p$, find $a$ such that $a^2 \equiv y \pmod p$.Solution. Calculate $(z+x)^{\frac{p-1}{2}} \pmod{x^2-y}$ for random $z \in \mathbb Z_p$ such that $z^2 \neq y$.If the result is $a_0 + a_1 x$ where $a_1 \neq 0$, then $a_0=0$ and $a=\frac{1}{a_1}$ is the solution.Tl;dr.Explanation.Due to Chinese remainder theorem, it is equivalent to computing $(z+x)^{\frac{p-1}{2}}$ modulo $x-a$ and $x+a$.Modulo $x-a$ it would be equal to $(z+a)^{\frac{p-1}{2}}$ and modulo $x+a$ it would be equal to $(z-a)^{\frac{p-1}{2}}$.If both are $1$ or both are $-1$, the result would be $1$ or $-1$ modulo $x^2-y$ as well.However if $z+a$ is a quadratic residue while $z-a$ is not (hence one makes $1$, the other makes $-1$), then $\begin{cases} a_0 + a_1 x \equiv 1 \pmod{x-a},\\ a_0 + a_1 x \equiv -1 \pmod{x+a} \end{cases} \implies a_0 = 0, a_1 = \frac{1}{a}.$Actual probability of success is at least $\frac{1}{2}$, you can find a proof in some book or paper or whatever.