Cipolla's algorithm
Introduction 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:'''* , an odd prime,* , which is a square. '''Outputs:'''* , satisfying Step 1 is to find an  such that  is not a square. There is no known deterministic algorithm for finding such an , but the following trial and error method can be used. 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 extension . 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 (Note: All elements before step two are considered as an element of  and all elements in step two are considered as elements of . )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. * Step 1: Find an ''a'' such that  is not a square. As stated, this has to be done by trial and error. Choose . Then  becomes 7.The Legendre symbol  has to be −1.Again this can be computed using Euler's criterion:  So  is a suitable choice for ''a''. * Step 2: Compute  in :::::So  is a solution, as well as . Indeed,
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 (with  being the analogon of ''i'').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 (which says that  for all ) 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  (in the case , the direct computation  is much faster) 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::: where  and : where ,  as in this article's exampleTaking 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 (See  here for mathematica code showing this above computation, rememberingthat something close to complex modular arithmetic is going on here) As such::   and and the final equation is::  which is the answer.
References
Sources * E. Bach, J.O. Shallit ''Algorithmic Number Theory: Efficient algorithms'' MIT Press, (1996)