One of the operations of modular arithmetic, and an important step in many algorithms of number theory, is finding modular square roots. In the expression x2 ≡ a (mod p), x is a modular square root of a; for instance, 62 is a square root of 2, mod 113, because 62 * 62 = 3844 = 36 * 113 + 2. Like real numbers, modular square roots come in pairs, so -62 ≡ 51 (mod 113) is also a square root of 2.
The usual method for finding modular square roots involves an algorithm developed by Alberto Tonelli in the 1890s; there are several variants, including one due to Daniel Shanks in 1973, one of which we saw in a previous exercise. The particular variant that we will look at today is described at http://www.math.vt.edu/people/brown/doc/sqrts.pdf.
We will assume that the modulus p = s · 2e + 1 is an odd prime, that the number a for which we seek a square root is coprime to p, and that the Legendre symbol (a/p) is 1, which indicates that the square root exists. Find an n such that n(p−1)/2 ≡ −1 (mod p); it won’t take long if you start from n = 2 and increase n by 1 until you find one. Then set x ≡ a(s+1)/2 (mod p), b ≡ as (mod p), g ≡ ns (mod p), and r = e. Next find the smallest non-negative integer m such that b2m ≡ 1 (mod p), which is done by repeated squarings and reductions. If m is zero, you’re finished; report the value of x and halt. Otherwise, set x to x · g2r−m−1 (mod p), set b to b · g2r−m (mod p), set g to g2r−m (mod p), and set r = m, then loop back and compute a new m, continuing until m is zero.
As an example we find the square root of 2 mod 113. First compute p = 113 = 7 · 24 + 1 and n = 3, then x = 16, b = 15, g = 40, and r = 4. The first computation of m is 2, so set x = 62, b = 1, g = 98, and r = 2. Then the second computation of m is 0, so x = 62 is a square root of 2 (mod 113), and so is 113 – 62 = 51.
Your task is to write a function that computes modular square roots according to the algorithm described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
div { margin-top: 1em; }
]]>
Pages: 1 2