In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form
formula_1
where formula_2, so "n" is the square of "x", and where formula_3 is an odd prime. Here formula_4 denotes the finite field with formula_3 elements; formula_6. 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 formula_11 such that formula_12 is not a square. There is no known deterministic algorithm for finding such an formula_13, but the following trial and error method can be used. Simply pick an formula_13 and by computing the Legendre symbol formula_15 one can see whether formula_13 satisfies the condition. The chance that a random formula_13 will satisfy is formula_18. With formula_3 large enough this is about formula_20. Therefore, the expected number of trials before finding a suitable formula_13 is about 2.
Step 2 is to compute "x" by computing formula_22 within the field extension formula_23. This "x" will be the one satisfying formula_24
If formula_25, then formula_26 also holds. And since "p" is odd, formula_27. So whenever a solution "x" is found, there's always a second solution, "-x".
Example.
Find all "x" such that formula_30
Before applying the algorithm, it must be checked that formula_31 is indeed a square in formula_28. Therefore, the Legendre symbol formula_33 has to be equal to 1. This can be computed using Euler's criterion: formula_34 This confirms 10 being a square and hence the algorithm can be applied.
formula_43
formula_44
formula_45
formula_46
So formula_47 is a solution, as well as formula_48. Indeed, formula_49
Proof.
The first part of the proof is to verify that formula_50 is indeed a field. For the sake of notation simplicity, formula_51 is defined as formula_52. Of course, formula_53 is a quadratic non-residue, so there is no square root in formula_4. This formula_51 can roughly be seen as analogous to the complex number i.
The field arithmetic is quite obvious. Addition is defined as
formula_56.
Multiplication is also defined as usual. With keeping in mind that formula_57, it becomes
formula_58.
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 formula_59 is somewhat resembles the field of complex numbers (with formula_51 being the analogon of "i"). ;br ;
The additive identity is formula_61, or more formally formula_62: Let formula_63, then
formula_64.
The multiplicative identity is formula_65, or more formally formula_66:
formula_67.
The only thing left for formula_59 being a field is the existence of additive and multiplicative inverses. It is easily seen that the additive inverse of formula_69 is formula_70, which is an element of formula_59, because formula_72. In fact, those are the additive inverse elements of "x" and "y". For showing that every non-zero element formula_73 has a multiplicative inverse, write down formula_74 and formula_75. In other words,
formula_76.
So the two equalities formula_77 and formula_78 must hold. Working out the details gives expressions for formula_79 and formula_80, namely
formula_81,
formula_82.
The inverse elements which are shown in the expressions of formula_79 and formula_80 do exist, because these are all elements of formula_4. This completes the first part of the proof, showing that formula_59 is a field.
The second and middle part of the proof is showing that for every element formula_87.
By definition, formula_88 is not a square in formula_4. Euler's criterion then says that
formula_90.
Thus formula_91. This, together with Fermat's little theorem (which says that formula_92 for all formula_93) and the knowledge that in fields of characteristic "p" the equation formula_94 holds, a relationship sometimes called the Freshman's dream, shows the desired result
formula_95.
The third and last part of the proof is to show that if formula_96, then formula_97. ;br ;
Compute
formula_98.
Note that this computation took place in formula_59, so this formula_100. 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 formula_101 has 2 roots in formula_4, these roots must be all of the roots in formula_59. It was just shown that formula_104 and formula_105 are roots of formula_101 in formula_59, so it must be that formula_108.
Speed.
After finding a suitable "a", the number of operations required for the algorithm is formula_109 multiplications, formula_110 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 formula_59, the following two equalities hold
formula_112
where formula_57 is known in advance. This computation needs 4 multiplications and 4 sums.
formula_114
where formula_115 and formula_116. This operation needs 6 multiplications and 4 sums.
Assuming that formula_117 (in the case formula_118, the direct computation formula_119 is much faster) the binary expression of formula_120 has formula_121 digits, of which "k" are ones. So for computing a formula_120 power of formula_123, the first formula has to be used formula_124 times and the second formula_125 times.
For this, Cipolla's algorithm is better than the Tonelli–Shanks algorithm if and only if formula_126, with formula_127 being the maximum power of 2 which divides formula_128.
Prime power moduli.
According to Dickson's "History Of Numbers", the following formula of Cipolla will find square roots modulo powers of prime:
formula_129
 where formula_130 and formula_131
 where formula_132, formula_133 as in this article's example
Taking the example in the wiki article we can see that this formula above does indeed take square roots modulo prime powers.
As
formula_134
Now solve for formula_135 via: 
formula_136
Now create the formula_137 and formula_138
(See for mathematica code showing this above computation, remembering
that something close to complex modular arithmetic is going on here) 
As such:
formula_139 and formula_140
and the final equation is:
formula_141 which is the answer.
References.
 ;templatestyles src="Reflist/styles.css" / ;