19 lines
645 B
Text
19 lines
645 B
Text
var BN=Import("zklBigNum");
|
|
fcn modEq(a,b,p) { (a-b)%p==0 }
|
|
fcn legendre(a,p){ a.powm((p - 1)/2,p) }
|
|
|
|
fcn tonelli(n,p){ //(BigInt,Int|BigInt)
|
|
_assert_(legendre(n,p)==1, "not a square (mod p)"+vm.arglist);
|
|
q,s:=p-1,0;
|
|
while(q.isEven){ q/=2; s+=1; }
|
|
if(s==1) return(n.powm((p+1)/4,p));
|
|
z:=[BN(2)..p].filter1('wrap(z){ legendre(z,p)==(p-1) });
|
|
c,r,t,m,t2:=z.powm(q,p), n.powm((q+1)/2,p), n.powm(q,p), s, 0;
|
|
while(not modEq(t,1,p)){
|
|
t2=(t*t)%p;
|
|
i:=1; while(not modEq(t2,1,p)){ i+=1; t2=(t2*t2)%p; } // assert(i<m)
|
|
b:=c.powm(BN(1).shiftLeft(m-i-1), p);
|
|
r,c,t,m = (r*b)%p, (b*b)%p, (t*c)%p, i;
|
|
}
|
|
r
|
|
}
|