Cipolla's algorithm

Cipolla's algorithm is used to solve a congruence of the form

$x^{2}\equiv n{\pmod {p}}$,

where $n\in \mathbf {F} _{p}$ is a quadratic residue and $p$ is an odd prime. Here $\mathbf {F} _{p}$ denotes the finite field $(\mathbb {Z} _{p},+,\cdot )$, which has $p$ elements; $\{0,1,...,p-1\}$. The algorithm is named after M. Cipolla, who discovered it in the year 1907.

The algorithm

Inputs:

• $p$, an odd prime,
• $n\in \mathbf {F} _{p}$, an integer which is a quadratic residue ${\pmod {p}}$.

Outputs:

• $x\in \mathbf {F} _{p}$, an integer satisfying $x^{2}\equiv n{\pmod {p}}$.

Step 1 is to find an $a\in \mathbf {F} _{p}$ such that $a^{2}-n$ is a quadratic non-residue ${\pmod {p}}$. There is no known algorithm for finding such an $a$, except the trial and error method. Simply pick an $a$ and by computing the Legendre symbol $(a^{2}-n|p)$ one can see whether $a$ satisfies the condition. The chance that a random $a$ will satisfy is $(p-1)/2p$. With $p$ large enough this is about $1/2$. Therefore, the expected number of trials before finding a suitable a is about 2.

Step 2 is to compute x by computing $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}$ within the field $\mathbf {F} _{p}({\sqrt {a^{2}-n}})$. This x will be the one satisfying $x^{2}\equiv n{\pmod {p}}$.

If $x^{2}\equiv n{\pmod {p}}$, then $(-x)^{2}\equiv n{\pmod {p}}$ also holds. And since p is odd, $x\neq -x{\pmod {p}}$. So whenever a solution x is found, there's always a second solution, -x.

Example

Find all x such that $x^{2}\equiv 10{\pmod {13}}$.

Before applying the algorithm, it must be checked that $10$ is indeed a quadratic residue ${\pmod {13}}$. Therefore, the Legendre symbol $(10|13)$ has to be equal to 1. This can be computed using Euler's criterion; $(10|13)=10^{6}\equiv 1{\pmod {13}}$. This confirms 10 being a quadratic residue ${\pmod {13}}$ and hence the algorithm can be applied.

• Step 1: Find an a such that $a^{2}-n$ is a quadratic non-residue ${\pmod {13}}$. As stated, this has to be done by trial and error. Choose $a=2$. Then $a^{2}-n$ becomes $7{\pmod {13}}$. The Legendre symbol $(7|13)$ has to be -1. Again this can be computed using Euler's criterion. $7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\pmod {13}}$. So $a=2$ is a suitable choice for a.
• Step 2: Compute $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}{\pmod {13}}$.

$\left(2+{\sqrt {-6}}\right)^{2}\equiv 4+4{\sqrt {-6}}-6\equiv -2+4{\sqrt {-6}}{\pmod {13}}$.

$\left(2+{\sqrt {-6}}\right)^{4}\equiv \left(-2+4{\sqrt {-6}}\right)^{2}\equiv -1-3{\sqrt {-6}}{\pmod {13}}$.

$\left(2+{\sqrt {-6}}\right)^{6}\equiv \left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)\equiv 9+2{\sqrt {-6}}{\pmod {13}}$.

$\left(2+{\sqrt {-6}}\right)^{7}\equiv \left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)\equiv 6+13{\sqrt {-6}}\equiv 6{\pmod {13}}$.

So $x\equiv 6{\pmod {13}}$ is a solution, as well as $x\equiv -6\equiv 7{\pmod {13}}$. Indeed, $6^{2}\equiv 36\equiv 10{\pmod {13}}$ and $7^{2}\equiv 49\equiv 10{\pmod {13}}$.

Proof

This is nice. This is very very very nice. Yes! The first part of the proof is to verify that $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}$ is indeed a field. For the sake of notation simplicity, $\omega$ is defined as ${\sqrt {a^{2}-n}}$. Of course, $a^{2}-n$ is a quadratic non-residue, so there is no square root in $\mathbf {F} _{p}$. This $\omega$ can roughly be seen as analogous to the complex number i. The field arithmetic is quite obvious. Addition is defined as

$\left(x_{1}+\omega y_{1}\right)+\left(x_{2}+\omega y_{2}\right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\omega$.

Multiplication is also defined as usual. With keeping in mind that $\omega ^{2}=a^{2}-n$, it becomes

$\left(x_{1}+y_{1}\omega \right)\left(x_{2}+y_{2}\omega \right)=x_{1}x_{2}+x_{1}y_{2}\omega +y_{1}x_{2}\omega +y_{1}y_{2}\omega ^{2}=\left(x_{1}x_{2}+y_{1}y_{2}\left(n^{2}-a\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega$.

Now the field properties have to be checked. The properties of closure under addition and multiplication, associativity, commutativity and distributivity are easily seen. This is because in this case the field $\mathbf {F} _{p^{2}}$ is somewhat equivalent to the field of complex numbers (with $\omega$ being the analogon of i).
The additive identity is $0$, more formal $0+0\omega$: Let $\alpha \in \mathbf {F} _{p^{2}}$, then

$\alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha$.

The multiplicative identity is $1$, or more formal $1+0\omega$:

$\alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot 0\left(n^{2}-a\right)\right)+(x\cdot 0+1\cdot x)\omega =x+y\omega =\alpha$.

The only thing left for $\mathbf {F} _{p^{2}}$ being a field is the existence of additive and multiplicative inverses. It is easily seen that the additive inverse of $x+y\omega$ is $-x-y\omega$, which is an element of $\mathbf {F} _{p^{2}}$, because $-x,-y\in \mathbf {F} _{p}$. In fact, those are the additive inverse elements of x and y. For showing that every non-zero element $\alpha$ has a multiplicative inverse, write down $\alpha =x_{1}+y_{1}\omega$ and $\alpha ^{-1}=x_{2}+y_{2}\omega$. In other words,

$(x_{1}+y_{1}\omega )(x_{2}+y_{2}\omega )=\left(x_{1}x_{2}+y_{1}y_{2}\left(n^{2}-a\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega =1$.

So the two equalities $x_{1}x_{2}+y_{1}y_{2}(n^{2}-a)=1$ and $x_{1}y_{2}+y_{1}x_{2}=0$ must hold. Working out the details gives expressions for $x_{2}$ and $y_{2}$, namely

$x_{2}=-y_{1}^{-1}x_{1}\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}$,

$y_{2}=\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}$.

The inverse elements which are shown in the expressions of $x_{2}$ and $y_{2}$ do exist, because these are all elements of $\mathbf {F} _{p}$. This completes the first part of the proof, showing that $\mathbf {F} _{p^{2}}$ is a field.

The second and middle part of the proof is showing that for every element $x+y\omega \in \mathbf {F} _{p^{2}}:(x+y\omega )^{p}=x-y\omega$. By definition, $\omega ^{2}$ is a quadratic non-residue. Euler's criterion then says that

$\omega ^{p-1}=\left(\omega ^{2}\right)^{\frac {p-1}{2}}=-1$.

Thus $\omega ^{p}=-\omega$. This, together with Fermat's little theorem (which says that $x^{p}=x$ for all $x\in \mathbf {F} _{p^{2}}$) shows the desired result

$(x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=x-y\omega$.

The third and last part of the proof is to show that if $x_{0}=\left(n+\omega \right)^{\frac {p+1}{2}}\in \mathbf {F} _{p^{2}}$, then $x_{0}^{2}=a\in \mathbf {F} _{p}$.
Compute

$x_{0}^{2}=\left(n+\omega \right)^{p+1}=(n+\omega )(n+\omega )^{p}=(n+\omega )(n-\omega )=n^{2}-\omega ^{2}=n^{2}-\left(n^{2}-a\right)=a$.

Note that this computation took place in $\mathbf {F} _{p^{2}}$, so this $x_{0}\in \mathbf {F} _{p^{2}}$. But with Lagrange's theorem, stating that a non-zero polynomial of degree n has at most n roots in any field K, and the knowledge that $x^{2}-a$ has 2 roots in $\mathbf {F} _{p}$, these roots must be all of the roots in $\mathbf {F} _{p^{2}}$. It was just shown that $x_{0}$ and $-x_{0}$ are roots of $x^{2}-a$ in $\mathbf {F} _{p^{2}}$, so it must be that $x_{0},-x_{0}\in \mathbf {F} _{p}$.

Q.E.D.