In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where
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.
[1] Inputs: Outputs: Step 1 is to find an
There is no known deterministic algorithm for finding such an
, but the following trial and error method can be used.
[2] Therefore, the expected number of trials before finding a suitable
This confirms 10 being a square and hence the algorithm can be applied.
The first part of the proof is to verify that
For the sake of notation simplicity,
is a quadratic non-residue, so there is no square root in
can roughly be seen as analogous to the complex number i.
The field arithmetic is quite obvious.
The properties of closure under addition and multiplication, associativity, commutativity and distributivity are easily seen.
is somewhat resembles the field of complex numbers (with
being a field is the existence of additive and multiplicative inverses.
In fact, those are the additive inverse elements of x and y.
Working out the details gives expressions for
, namely The inverse elements which are shown in the expressions of
This completes the first part of the proof, showing that
The second and middle part of the proof is showing that for every element
) 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
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
[3] After finding a suitable a, the number of operations required for the algorithm is
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.
is much faster) the binary expression of
[4] According to Dickson's "History Of Numbers", the following formula of Cipolla will find square roots modulo powers of prime: [5] [6] Taking the example in the wiki article we can see that this formula above does indeed take square roots modulo prime powers.
(See here for mathematica code showing this above computation, remembering that something close to complex modular arithmetic is going on here) As such: and the final equation is: