Talk:Cipolla's algorithm
Appearance
![]() | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
[Untitled]
[edit]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
[edit]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]
- where and
- where , 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?
[edit]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)
I quote from the article itself:
- "Step 1 is to find an such that is not a square"