def _sqrt_mod_tonelli_shanks(a, p):
 s = trailing((p - 1))
 t = (p >> s)
 while 1:
  d = randint(2, (p - 1))
  r = legendre_symbol(d, p)
  if (r == (-1)):
   break
 A = pow(a, t, p)
 D = pow(d, t, p)
 m = 0
 for i in range(s):
  adm = ((A * pow(D, m, p)) % p)
  adm = pow(adm, (2 ** ((s - 1) - i)), p)
  if ((adm % p) == (p - 1)):
   m += (2 ** i)
 x = ((pow(a, ((t + 1) // 2), p) * pow(D, (m // 2), p)) % p)
 return x

def _sqrt_mod_tonelli_shanks ( a , p ) : s = trailing ( ( p - 1 ) ) t = ( p >> s ) while 1 : d = randint ( 2 , ( p - 1 ) ) r = legendre_symbol ( d , p ) if ( r == ( - 1 ) ) : break A = pow ( a , t , p ) D = pow ( d , t , p ) m = 0 for i in range ( s ) : adm = ( ( A * pow ( D , m , p ) ) % p ) adm = pow ( adm , ( 2 ** ( ( s - 1 ) - i ) ) , p ) if ( ( adm % p ) == ( p - 1 ) ) : m += ( 2 ** i ) x = ( ( pow ( a , ( ( t + 1 ) // 2 ) , p ) * pow ( D , ( m // 2 ) , p ) ) % p ) return x
returns the square root in the case of p prime with p == 1 references .