A slightly faster algorithm for finding square root modulo an odd prime

Revision en1, by hly1204, 2022-01-10 08:33:07

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)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English hly1204 2022-01-10 18:48:29 201
en1 English hly1204 2022-01-10 08:33:07 1765 Initial revision (published)