Acceptance sampling

2013-12-12T06:58:50Z

117.194.4.149:

In [[computational number theory]], '''Cipolla's algorithm''' is a technique for solving a [[Congruence relation|congruence]] of the form

:<math>x^2\equiv n \pmod{p}.</math>

where <math>x,n \in \mathbf{F}_{p}</math>, so ''n'' is the square of ''x'', and where <math>p</math> is an [[Parity (mathematics)|odd]] [[Prime number|prime]]. Here <math>\mathbf{F}_p</math> denotes the finite [[Field (mathematics)|field]] with <math>p</math> [[Element (mathematics)|elements]]; <math>\{0,1,\dots,p-1\}</math>. The [[algorithm]] is named after [[Michele Cipolla]], an [[Italy|Italian]] [[Mathematics|mathematician]] who discovered it in the year 1907.

==The algorithm==

'''Inputs:'''
*<math>p</math>, an odd prime,
*<math>n \in \mathbf{F}_p</math>, which is a square.

'''Outputs:'''
*<math>x \in \mathbf{F}_p</math>, satisfying <math> x^2= n . </math>

Step 1 is to find an <math>a \in \mathbf{F}_p</math> such that <math>a^2 - n</math> is not a square. There is no known algorithm for finding such an <math>a</math>, except the [[trial and error]] method. Simply pick an <math>a</math> and by computing the [[Legendre symbol]] <math>(a^2-n|p)</math> one can see whether <math>a</math> satisfies the condition. The chance that a random <math>a</math> will satisfy is <math>(p-1)/2p</math>. With <math>p</math> large enough this is about <math>1/2</math>.<ref>R. Crandall, C. Pomerance Prime Numbers: A Computational Perspective Springer-Verlag, (2001) p. 157</ref> Therefore, the expected number of trials before finding a suitable ''a'' is about 2.

Step 2 is to compute ''x'' by computing <math>x=\left( a + \sqrt{a^2-n} \right)^{(p+1)/2}</math> within the field <math>\mathbf{F}_{p^2} = \mathbf{F}_p(\sqrt{a^2-n})</math>. This ''x'' will be the one satisfying <math> x^2 =n .</math>

If <math>x^2 = n</math>, then <math>(-x)^2 = n</math> also holds. And since ''p'' is odd, <math> x \neq -x </math>. 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 <math>\mathbf{F}_{13}</math> and all elements in step two are considered as elements of <math>\mathbf{F}_{13^2}</math>).

Find all ''x'' such that <math>x^2 = 10.</math>

Before applying the algorithm, it must be checked that <math>10</math> is indeed a square in <math>\mathbf{F}_{13}</math>. Therefore, the Legendre symbol <math>(10 | 13)</math> has to be equal to 1. This can be computed using [[Euler's criterion]]; <math>(10 | 13) \equiv 10^6 \equiv 1 \bmod 13.</math> This confirms 10 being a square and hence the algorithm can be applied.

* Step 1: Find an ''a'' such that <math>a^2 - n</math> is not a square. As stated, this has to be done by trial and error. Choose <math>a=2</math>. Then <math>a^2 - n</math> becomes 7. The Legendre symbol <math>(7 | 13)</math> has to be -1. Again this can be computed using Euler's criterion. <math>7^6 = 343^2 \equiv 5^2 \equiv 25 \equiv -1 \bmod 13.</math> So <math>a=2</math> is a suitable choice for ''a''.
* Step 2: Compute <math>x = \left( a + \sqrt{a^2-n} \right)^{(p+1)/2} = \left( 2 + \sqrt{-6}\right)^7 .</math>

:<math>\left(2+\sqrt{-6}\right)^2 = 4 + 4\sqrt{-6} - 6 = -2 + 4 \sqrt{-6} .</math>
:<math>\left(2+\sqrt{-6}\right)^4 = \left(-2+4\sqrt{-6}\right)^2 = -1-3\sqrt{-6} .</math>
:<math>\left(2+\sqrt{-6}\right)^6 = \left(-2 + 4\sqrt{-6}\right)\left(-1-3\sqrt{-6}\right) = 9+2\sqrt{-6} .</math>
:<math>\left(2+\sqrt{-6}\right)^7 = \left(9+2\sqrt{-6}\right)\left(2+ \sqrt{-6}\right) = 6 .</math>

So <math>x = 6 </math> is a solution, as well as <math>x = -6 = 7 .</math> Indeed, <math>6^2 = 36 = 10</math> and <math> 7^2= 49 = 10 .</math>

==Proof==

The first part of the proof is to verify that <math>\mathbf{F}_{p^2} = \mathbf{F}_p(\sqrt{a^2-n}) = \{x + y\sqrt{a^2-n} : x,y \in \mathbf{F}_p\}</math> is indeed a field. For the sake of notation simplicity, <math>\omega</math> is defined as <math>\sqrt{a^2-n}</math>. Of course, <math>a^2-n</math> is a quadratic non-residue, so there is no [[square root]] in <math>\mathbf{F}_p</math>. This <math>\omega</math> can roughly be seen as analogous to the complex number [[Imaginary unit|i]].
The field arithmetic is quite obvious. [[Addition]] is defined as
:<math>\left(x_1 + y_1 \omega \right) + \left(x_2 + y_2 \omega \right) = \left(x_1 + x_2 \right) + \left(y_1 + y_2\right) \omega</math>.
[[Multiplication]] is also defined as usual. With keeping in mind that <math>\omega^2 = a^2-n</math>, it becomes
:<math>\left(x_1 + y_1 \omega \right)\left(x_2 + y_2 \omega \right) = x_1 x_2 + x_1 y_2 \omega + y_1 x_2 \omega + y_1 y_2 \omega^2 = \left( x_1 x_2 + y_1 y_2 \left(a^2-n\right)\right) + \left(x_1 y_2 + y_1 x_2 \right) \omega</math>.
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 <math>\mathbf{F}_{p^2}</math> is somewhat equivalent to the field of [[complex number]]s (with <math>\omega</math> being the analogon of ''i'').<br>
The additive [[Identity element|identity]] is <math>0</math>, more formal <math>0 + 0\omega</math>: Let <math>\alpha \in \mathbf{F}_{p^2}</math>, then
:<math>\alpha + 0 = (x+y\omega) + (0 + 0\omega) = (x + 0) + (y + 0)\omega = x+y\omega = \alpha</math>.
The multiplicative identity is <math>1</math>, or more formal <math> 1 + 0\omega</math>:
:<math>\alpha \cdot 1 = (x+y\omega)(1 + 0\omega) = \left(x\cdot 1 + 0 \cdot 0 \left(n^2-a\right)\right) + (x\cdot 0 + 1 \cdot x)\omega = x+y\omega = \alpha</math>.
The only thing left for <math>\mathbf{F}_{p^2}</math> being a field is the existence of additive and multiplicative [[Inverse element|inverses]]. It is easily seen that the additive inverse of <math>x+y\omega</math> is <math>-x-y\omega</math>, which is an element of <math>\mathbf{F}_{p^2}</math>, because <math>-x,-y \in \mathbf{F}_p</math>. In fact, those are the additive inverse elements of ''x'' and ''y''. For showing that every non-zero element <math>\alpha</math> has a multiplicative inverse, write down <math>\alpha = x_1 + y_1 \omega</math> and <math>\alpha^{-1} = x_2 + y_2 \omega</math>. In other words,
:<math>(x_1 + y_1 \omega)(x_2 + y_2 \omega) = \left( x_1 x_2 + y_1 y_2 \left(n^2-a\right)\right) + \left(x_1 y_2 + y_1 x_2 \right) \omega = 1</math>.
So the two equalities <math>x_1x_2 + y_1y_2(n^2-a) = 1</math> and <math>x_1y_2 + y_1x_2 = 0</math> must hold. Working out the details gives expressions for <math>x_2</math> and <math>y_2</math>, namely
:<math>x_2 = -y_1^{-1}x_1\left(y_1\left(n^2-a\right)-x_1^2y_1^{-1}\right)^{-1}</math>,
:<math>y_2 = \left( y_1 \left(n^2-a\right) - x_1^2y_1^{-1}\right)^{-1}</math>.
The inverse elements which are shown in the expressions of <math>x_2</math> and <math>y_2</math> do exist, because these are all elements of <math>\mathbf{F}_p</math>. This completes the first part of the proof, showing that <math>\mathbf{F}_{p^2}</math> is a field.

The second and middle part of the proof is showing that for every element <math>x+y\omega \in \mathbf{F}_{p^2} : (x+y\omega)^p = x - y\omega</math>.
By definition, <math>\omega^2=a^2-n</math> is not a square in <math>\mathbf{F}_p</math>. Euler's criterion then says that
:<math>\omega^{p-1} = \left(\omega^2\right)^{\frac{p-1}{2}} = -1</math>.
Thus <math>\omega^p = -\omega</math>. This, together with [[Fermat's little theorem]] (which says that <math>x^p = x</math> for all <math>x \in \mathbf{F}_{p}</math>) and the knowledge that in fields of [[Characteristic (algebra)|characteristic]] ''p'' the equation <math>\left(a+b\right)^p = a^p + b^p</math> holds, shows the desired result
:<math>(x+y\omega)^p = x^p + y^p \omega^p = x - y\omega</math>.

The third and last part of the proof is to show that if <math>x_0=\left(a+\omega \right)^{\frac{p+1}{2}} \in \mathbf{F}_{p^2}</math>, then <math>x_0^2=n \in \mathbf{F}_p</math>.<br>
Compute
:<math>x_0^2 = \left(a+\omega \right)^{p+1} = (a+\omega)(a+\omega)^{p}=(a+\omega)(a-\omega)=a^2 - \omega^2 = a^2 - \left(a^2 - n \right) = n</math>.
Note that this computation took place in <math>\mathbf{F}_{p^2}</math>, so this <math>x_0 \in \mathbf{F}_{p^2}</math>. But with [[Lagrange's theorem (number theory)|Lagrange's theorem]], stating that a non-zero [[Integer polynomial|polynomial]] of degree ''n'' has at most ''n'' roots in any field ''K'', and the knowledge that <math>x^2-n</math> has 2 roots in <math>\mathbf{F}_p</math>, these roots must be all of the roots in <math>\mathbf{F}_{p^2}</math>. It was just shown that <math>x_0</math> and <math>-x_0</math> are roots of <math>x^2-n</math> in <math>\mathbf{F}_{p^2}</math>, so it must be that <math>x_0, -x_0 \in \mathbf{F}_p</math>.<ref>[http://people.math.gatech.edu/~mbaker/pdf/cipolla2011.pdf M. Baker ''Cipolla's Algorithm for finding square roots mod p'']</ref>

==Speed of the algorithm==
After finding a suitable ''a'', the number of operations required for the algorithm is <math>4m + 2k - 4</math> multiplications, <math>4m-2</math> sums, where ''m'' is the number of [[Numerical digit|digits]] in the [[Binary numeral system|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 <math>\mathbf{F}_{p^2}</math>, the following two equalities hold
:<math>(x+y\omega)^2 = \left(x^2 + y^2 \omega^2 \right) + \left(\left(x+y\right)^2-x^2-y^2\right)\omega,</math>
where <math>\omega^2 = a^2-n</math> is known in advance. This computation needs 4 multiplications and 4 sums.
:<math>\left(x+y\omega\right)^2\left(c + \omega \right) = \left( cd - b\left(x+d\right)\right) + \left(d^2 - by\right)\omega,</math>
where <math>d=(x+yc)</math> and <math>b=ny</math>. This operation needs 6 multiplications and 4 sums.

Assuming that <math>p \equiv 1 \pmod 4,</math> (in the case <math>p \equiv 3 \pmod 4</math>, the direct computation <math>x \equiv \pm n^{\frac{p+1}{4}}</math> is much faster) the binary expression of <math>(p+1)/2</math> has <math>m-1</math> digits, of which ''k'' are ones. So for computing a <math>(p+1)/2</math> power of <math>\left(a + \omega \right)</math>, the first formula has to be used <math>n-k-1</math> times and the second <math>k-1</math> times.

For this, Cipolla's algorithm is better than the [[Tonelli-Shanks algorithm]] if and only if <math>S(S-1) > 8m+20</math>, with <math>2^{S}</math> being the maximum power of 2 which divides <math>p-1</math>.<ref>[http://www.springerlink.com/content/xgxe68edy03la96p/fulltext.pdf Gonzalo Tornaria ''Square roots modulo p'']</ref>

==References==

<references/>
* E. Bach, J.O. Shallit ''Algorithmic Number Theory: Efficient algorithms'' MIT Press, (1996)

{{number theoretic algorithms}}

[[Category:Modular arithmetic]]
[[Category:Number theoretic algorithms]]
[[Category:Articles containing proofs]]

formulasearchengine - User contributions [en]

Acceptance sampling