1 # from http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/
3 def modular_sqrt(a, p):
4 """ Find a quadratic residue (mod p) of 'a'. p
7 Solve the congruence of the form:
9 And returns x. Note that p - x is also a root.
11 0 is returned is no square root exists for
14 The Tonelli-Shanks algorithm is used (except
15 for some simple cases in which the solution
16 is known from an identity). This algorithm
17 runs in polynomial time (unless the
18 generalized Riemann hypothesis is false).
22 if legendre_symbol(a, p) != 1:
29 return pow(a, (p + 1) / 4, p)
31 # Partition p-1 to s * 2^e for an odd s (i.e.
32 # reduce all the powers of 2 from p-1)
40 # Find some 'n' with a legendre symbol n|p = -1.
41 # Shouldn't take long.
44 while legendre_symbol(n, p) != -1:
48 # Read the paper "Square roots from 1; 24, 51,
49 # 10 to Dan Shanks" by Ezra Brown for more
53 # x is a guess of the square root that gets better
54 # with each iteration.
55 # b is the "fudge factor" - by how much we're off
56 # with the guess. The invariant x^2 = ab (mod p)
57 # is maintained throughout the loop.
58 # g is used for successive powers of n to update
60 # r is the exponent - decreases with each update
62 x = pow(a, (s + 1) / 2, p)
78 gs = pow(g, 2 ** (r - m - 1), p)
84 def legendre_symbol(a, p):
85 """ Compute the Legendre symbol a|p using
86 Euler's criterion. p is a prime, a is
87 relatively prime to p (if p divides
90 Returns 1 if a has a square root modulo
93 ls = pow(a, (p - 1) / 2, p)
94 return -1 if ls == p - 1 else ls