1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| def multiplication(x1,y1,x2,y2,w,p): x=(x1*x2+y1*y2*w)%p y=(x1*y2+x2*y1)%p return x,y
def get_w(c,p): a=randint(1,p) w=pow(a, 2) - c while pow(w,(p - 1)/ 2,p)! p-1: a=randint(1,p) w=pow(a,2)-c return w,a def Cipolla_algorithm(c,p): w,a=get_w(c,p) power=(p+1)/ 2 x1=a y1=1 x=1 y=0 while(power! 0): if(power! (p+1)/ 2): x1,y1=multiplication(x1,y1,x1,y1,w,p) if(power & 1): x,y=multiplication(x,y,x1,y1,w,p) power> 1 return x cn = pow(c,4*1534022146892150554839736212812313821410100326022914405108745499241300613161518580076912 4140840468748 23035337005158475621433705623268639417140515158078335142054666787229183797173181186377993649280, n) cp = cn%p Cipolla_algorithm(cn,p)%p 166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259 694276272602506054433757749654828608600573448732931745676174 sage: Cipolla_algorithm(cn,p)%p 132092561537869160993667319333430266730451609506565594486832556247939179580442437134355292265094 6388889883899419614130483678902025 sage: Cipolla_algorithm(cn,p)%p 166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259 694276272602506054433757749654828608600573448732931745676174 sage: Cipolla_algorithm(166353789373057352195268573847472134983952212264580315606750168640904529917560 511398152614100259694276272602506054433757749654828608600573448732931745676174,p)%p 0 sage: Cipolla_algorithm(132092561537869160993667319333430266730451609506565594486832556247939179580442 4371343552922650946388889883899419614130483678902025,p)%p 36344540379246669047243921781711114415694316462518391812884210045 sage: Cipolla_algorithm(132092561537869160993667319333430266730451609506565594486832556247939179580442 4371343552922650946388889883899419614130483678902025,p)%p 166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176543306 949701450304802363434626984929302798183530544471602540368154
PYTHON
|