Cipolla's algorithm


In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form
where, so n is the square of x, and where is an odd prime. Here denotes the finite field with elements;. The algorithm is named after Michele Cipolla, an Italian mathematician who discovered it in 1907.
Apart from prime moduli, Cipolla's algorithm is also able to take square roots modulo prime powers.

Algorithm

Inputs:
Outputs:
Step 1 is to find an such that is not a square. There is no known algorithm for finding such an, except the trial and error method. Simply pick an and by computing the Legendre symbol one can see whether satisfies the condition. The chance that a random will satisfy is. With large enough this is about. Therefore, the expected number of trials before finding a suitable is about 2.
Step 2 is to compute x by computing within the field. This x will be the one satisfying
If, then also holds. And since p is odd,. So whenever a solution x is found, there's always a second solution, -x.

Example

.
Find all x such that
Before applying the algorithm, it must be checked that is indeed a square in. Therefore, the Legendre symbol has to be equal to 1. This can be computed using Euler's criterion; This confirms 10 being a square and hence the algorithm can be applied.
So is a solution, as well as Indeed, and

Proof

The first part of the proof is to verify that is indeed a field. For the sake of notation simplicity, is defined as. Of course, is a quadratic non-residue, so there is no square root in. This can roughly be seen as analogous to the complex number i.
The field arithmetic is quite obvious. Addition is defined as
Multiplication is also defined as usual. With keeping in mind that, it becomes
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 is somewhat resembles the field of complex numbers.
The additive identity is, or more formally : Let, then
The multiplicative identity is, or more formally :
The only thing left for being a field is the existence of additive and multiplicative inverses. It is easily seen that the additive inverse of is, which is an element of, because. In fact, those are the additive inverse elements of x and y. For showing that every non-zero element has a multiplicative inverse, write down and. In other words,
So the two equalities and must hold. Working out the details gives expressions for and, namely
The inverse elements which are shown in the expressions of and do exist, because these are all elements of. This completes the first part of the proof, showing that is a field.
The second and middle part of the proof is showing that for every element.
By definition, is not a square in. Euler's criterion then says that
Thus. This, together with Fermat's little theorem and the knowledge that in fields of characteristic p the equation holds, a relationship sometimes called the Freshman's dream, shows the desired result
The third and last part of the proof is to show that if, then.
Compute
Note that this computation took place in, so this. 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 has 2 roots in, these roots must be all of the roots in. It was just shown that and are roots of in, so it must be that.

Speed

After finding a suitable a, the number of operations required for the algorithm is multiplications, sums, where m is the number of digits in the binary representation of p and k is the number of ones in this representation. To find a by trial and error, the expected number of computations of the Legendre symbol is 2. But one can be lucky with the first try and one may need more than 2 tries. In the field, the following two equalities hold
where is known in advance. This computation needs 4 multiplications and 4 sums.
where and. This operation needs 6 multiplications and 4 sums.
Assuming that the binary expression of has digits, of which k are ones. So for computing a power of, the first formula has to be used times and the second times.
For this, Cipolla's algorithm is better than the Tonelli–Shanks algorithm if and only if, with being the maximum power of 2 which divides.

Prime power moduli

According to Dickson's "History Of Numbers", the following formula of Cipolla will find square roots modulo powers of prime:
Taking the example in the wiki article we can see that this formula above does indeed take square roots modulo prime powers.
As
Now solve for via:
Now create the and

As such:
and the final equation is: