二次剩余系解法

(Note: All $equiv$ are taken to mean $pmod p$ , unless indicated otherwise).[edit]The algorithm

Inputs: p, an odd prime. n, an integer which is a quadratic residue (mod p), meaning that the Legendre symbol $igl( frac{n}{p}igr)=1$ .

Outputs: R, an integer satisfying $R^2 equiv n$ .

Factor out powers of 2 from p − 1, defining Q and S as: $p-1 = Q2^S$ with Q odd. Note that if $S = 1$ , i.e. $p equiv 3 pmod 4$ , then solutions are given directly by $R equiv pm n^{frac{p+1}{4}}$ .
Select a z such that the Legendre symbol $igl( frac{z}{p}igr)=-1$ (that is, z should be a quadratic non-residue modulo p), and set $c equiv z^Q$ .
Let $R equiv n^{frac{Q+1}{2}}, tequiv n^Q, M = S.$
Loop:
1. If $t equiv 1$ , return R.
2. Otherwise, find the lowest i, $0 < i < M$ , such that $t^{2^i} equiv 1$ ; e.g. via repeated squaring.
3. Let $b equiv c^{2^{M-i-1}}$ , and set $R equiv Rb, ; t equiv tb^2, c equiv b^2$ and $M =; i$ .

Once you have solved the congruence with R the second solution is p − R.

Example

Solving the congruence $x^2 equiv 10 pmod {13}$ . It is clear that $13$ is odd, and since $10^{frac{13-1}{2}} = 10^6 equiv 1 pmod {13}$ , 10 is a quadratic residue (by Euler's criterion).

Step 1: Observe $p-1 = 12 = 3 cdot 2^2$ so $Q=3$ , $S=2$ .

Step 2: Take $z=2$ as the quadratic nonresidue (2 is a quadratic nonresidue since $2^{frac{13-1}{2}} = -1 pmod {13}$ (again, Euler's criterion)). Set $c = 2^3 equiv 8 pmod {13}.$

Step 3: $R=10^2 equiv -4, ; tequiv 10^3 equiv -1 pmod {13}, M = 2.$

Step 4: Now we start the loop: $t otequiv 1 pmod {13}$ so $0 < i <; 2$ ; i.e. $i = ;1.$
- Let $b equiv 8^{2^{2-1-1}} equiv 8 pmod {13}$ , so $b^2 equiv 8^2 equiv -1 pmod {13}$ .
- Set $R=-4cdot8 equiv 7 pmod {13}$ . Set $t equiv -1 cdot -1 equiv 1 pmod {13}$ , and $M =;1.$
- We restart the loop, and since $t equiv 1 pmod{13}$ we are done, returning $Requiv7 pmod {13}.$

Indeed, observe that $7^2 = 49 equiv 10 pmod {13}$ and naturally also $(-7)^2 equiv 6^2 equiv 10 pmod {13}$ . So the algorithm yields two solutions to our congruence.

Proof

First write $p-1=Q2^S$ . Now write $r equiv n^{frac{Q+1}{2}}pmod p$ and $t equiv n^Q pmod p$ , observing that $r^2 equiv nt pmod p$ . This latter congruence will be true after every iteration of the algorithm's main loop. If at any point, $t equiv 1 pmod p$ then $r^2 equiv n pmod p$ and the algorithm terminates with $R equiv pm r pmod p$ .

If $t otequiv 1 pmod p$ , then consider $z$ , a quadratic non-residue of $p$ . Let $c equiv z^Q pmod p$ . Then $c^{2^S} equiv (z^Q)^{2^S} equiv z^{2^SQ}equiv z^{p-1} equiv 1 pmod p$ and $c^{2^{S-1}} equiv z^frac{p-1}{2}equiv -1 pmod p$ , which shows that the order of $c$ is $2^S$ .

Similarly we have $t^{2^S} equiv 1 pmod p$ , so the order of $t$ divides $2^S$ . Suppose the order of $t$ is $2^{S'}$ . Since $n$ is a square modulo $p$ , $t equiv n^Q pmod p$ is also a square, and hence $S'leq S-1$ .

Now we set $b equiv c^{2^{S-S'-1}} pmod p$ and with this $r' equiv br pmod p$ , $c' equiv b^2 pmod p$ and $t' equiv c't pmod p$ . As before, $r'^2 equiv nt' pmod p$ holds; however with this construction both $t$ and $c'$ have order $2^{S'}$ . This implies that $t'$ has order $2^{S''}$ with $S'' < S'$ .

If $S'' equiv 0 pmod p$ then $t' equiv 1 pmod p$ , and the algorithm stops, returning $R equiv pm r' pmod p$ . Else, we restart the loop with analogous definitions of $b'$ , $r''$ , $c''$ and $t''$ until we arrive at an $S^{(j)'}$ that equals 0. Since the sequence of S is strictly decreasing the algorithm terminates.