Cipolla's algorithm
Encyclopedia
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 the year 1907.
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 a 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.
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.
So
is a solution, as well as 
Indeed, 
and 
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 equivalent to the field of complex number
s (with
being the analogon of i).
The additive identity
is
, more formal 
: Let 
, then
.
The multiplicative identity is
, or more formal 
:
.
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, 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 
.
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 
.
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
, Cipolla's algorithm is a technique for solving a congruence
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
of the form
where
, so n is the square of x, and where is an odd primePrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. Here
denotes the finite fieldField (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
with
elements; . The algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
is named after Michele Cipolla
Michele Cipolla
Michele Cipolla was an Italian mathematician, mainly specializing in number theory.He was a professor of Algebraic Analysis at the University of Catania and, later, the University of Palermo...
, an Italian
Italy
Italy , officially the Italian Republic languages]] under the European Charter for Regional or Minority Languages. In each of these, Italy's official name is as follows:;;;;;;;;), is a unitary parliamentary republic in South-Central Europe. To the north it borders France, Switzerland, Austria and...
mathematician
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
who discovered it in the year 1907.
The 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 algorithm for finding such an , except the trial and errorTrial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
method. Simply pick an
and by computing the Legendre symbolLegendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....
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 a 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
(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 criterionEuler's criterion
In mathematics, Euler's criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime.-Definition:Euler's criterion states:Let p be an odd prime and a an integer coprime to p. Then...
;
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
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 rootSquare root
In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
in
. This can roughly be seen as analogous to the complex number iImaginary unit
In mathematics, the imaginary unit allows the real number system ℝ to be extended to the complex number system ℂ, which in turn provides at least one root for every polynomial . The imaginary unit is denoted by , , or the Greek...
.
The field arithmetic is quite obvious. Addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
is defined as
.Multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
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
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
, commutativity
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
and distributivity
Distributivity
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
are easily seen. This is because in this case the field
is somewhat equivalent to the field of complex numberComplex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s (with
being the analogon of i).The additive identity
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
is
, more formal : Let , then.The multiplicative identity is
, or more formal :.The only thing left for
being a field is the existence of additive and multiplicative inversesInverse element
In abstract algebra, the idea of an inverse element generalises the concept of a negation, in relation to addition, and a reciprocal, in relation to multiplication. The intuition is of an element that can 'undo' the effect of combination with another given element...
. 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 theoremFermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
(which says that
for all ) and the knowledge that in fields of characteristicCharacteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
p the equation
holds, 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 theoremLagrange's theorem (number theory)
In number theory, Lagrange's theorem states that:If the modulus is not prime, then it is possible for there to be more than n solutions. The exact number of solutions can be determined by finding the prime factorization of n...
, 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 of the algorithm
After finding a suitable a, the number of operations required for the algorithm is multiplications, sums, where m is the number of digitsNumerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
in the binary representation
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
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 holdwhere
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 .