Talk:Cipolla's algorithm

[Untitled]

1. x^2 = 10; in F_13 the Legendre symbol also is 1 in (10|3). Why 13?

2. (10|13) = 10^6 mod 13; Why 6? Wrom where this number?

3. a = 2; n = 10; a^2-n = 4-10 = -6. Why a = 2?

4. a^2-n = 7; the Legendre symbol (7|10) But 2^2-10 = -6, not 7. Why 7?

Cipolla's algorithm is able to find square roots of powers of prime modula

According to Dickson's "History Of Numbers" vol 1 p 218, the following formula of Cipolla will find square roots of powers of prime modula: ^[1]

2^{-1}*q^{t}((k+{\sqrt {k^{2}-q}})^{s}+(k-{\sqrt {k^{2}-q}})^{s}){\bmod {p^{\lambda }}}

where

t=(p^{\lambda }-2*p^{\lambda -1}+1)/2

and

s=p^{\lambda -1}*(p+1)/2

where

q=10

,

k=2

as in the wiki example

Taking the example in the wiki article we can see that this formula above does indeed take square roots of prime power modula.

Dropping into Mathematica

PowerMod[10, 1/2, 13 13 13]=1046

Create 2^(-1)*q^(t) via
Mod[PowerMod[2, -1, 13 13 13] PowerMod[10, (13 13 13 - 2 13 13 + 1)/2,
    13 13 13], 13 13 13]=1086

Create the (k+ sqrt{k^{2}-q})^{s} and (k- sqrt{k^{2}-q})^{s} via the following Mathematica procedure 

try999[m_, r_, i_, p_, i1_] := 
 Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10},
  a2 = r;
  a3 = i;
  
  For[a1 = 2, a1 <= p , a1++,
   a4 = a2;
   a5 = a3;
   a2 = Mod[a4 r + a5 i i1, m];
   a3 = Mod[(a4 i + a3 r), m];
   (*Print[{a2,a3,a1}];*)
   ];
  Return[{a2, a3}];
  ]

(k+sqrt{k^{2}-q})^{s}= 1540   and (k-\sqrt{k^{2}-q})^{s}= 1540

via the following function calls

try999[13 13 13, 2, 1, 13 13 7, -6]=1540

try999[13 13 13, 2, -1, 13 13 7, -6]=1540

and 

Mod[1086 (2 1540), 13 13 13]=1046  which is the answer.

References

^ "History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p218 https://archive.org/stream/historyoftheoryo01dick#page/218/mode/2up

What if a^2-n is a square?

If a is chosen such that a^2-n is a square, and follow the algorithm, what will happen? Jackzhp (talk) 05:57, 16 January 2018 (UTC)[reply]

I quote from the article itself:

"Step 1 is to find an

a\in \mathbf {F} _{p}

such that

a^{2}-n

is not a square"

Endo999 (talk) 06:51, 16 January 2018 (UTC)[reply]

someone should check m. bakers title in source for cipolla modular square root article

The Russian ruwiki has m. baker's article title to be

M. Baker Cipolla's Algorithm for finding square roots mod p

but the enwiki article has the source title to be

M. Baker Cipolla's Algorithm for finding square roots mod p^n

somebody should check what is the actual correct title of this source Endo999 (talk) 01:45, 25 June 2025 (UTC)[reply]

[dickson-1] "History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p218 https://archive.org/stream/historyoftheoryo01dick#page/218/mode/2up

[1]