Talk:Cipolla's algorithm

This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

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?

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]

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

where ${\displaystyle t=(p^{\lambda }-2*p^{\lambda -1}+1)/2}$ and ${\displaystyle s=p^{\lambda -1}*(p+1)/2}$

where ${\displaystyle q=10}$,${\displaystyle 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.

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 ${\displaystyle a\in \mathbf {F} _{p}}$ such that ${\displaystyle a^{2}-n}$ is not a square"

Endo999 (talk) 06:51, 16 January 2018 (UTC)Reply

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

sorry my eyes were bad . the ^N I thought I saw was actually "

so the article title is correct as

M. Baker Cipolla's Algorithm for finding square roots mod p Endo999 (talk) 01:46, 25 June 2025 (UTC)Reply