Меню

Главная
Случайная статья
Настройки
Обсуждение:Алгоритм Чиполлы
Материал из https://ru.wikipedia.org

Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями.

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]
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.


Endo999 (обс.) 23:31, 31 января 2018 (UTC)[ответить]
  1. "History of the Theory of Numbers" Volume 1 by Leonard Eugene Dickson, p218 url=https://ia800209.us.archive.org/12/items/historyoftheoryo01dick/historyoftheoryo01dick.pdf
Downgrade Counter