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
}