Quadratic Residue EquationsDate: 11/21/2009 at 15:07:14 From: Steve Subject: Attacking quad residue eqn when p = 8n+1. Devise a method for solving the congruence x^2 == a (mod p) if the prime p == 1 (mod 8) and one quadratic nonresidue of p is known. Solve the congruence x^2 + 7 == 0 (mod 281) by using the fact that 3N281... Answer: x == +- 67 (mod 281). My flawed approach: Solve x^2 == a (mod prime p = 8n+1), given that g is a quadratic nonresidue of p: Let e denote g^{-1}a (mod p) and let A denote the index of g with respect to e ==>> [since g is a nonresidue] A is odd and a == e^{A+1} (mod p) ==>> x == +- e^{(A+1)/2}. In particular, with p,a,g = 281,-7,3, respectively, e = 94(-7) == 185 (mod 281) and 185^{41} == 3 (mod 281) ==>> x == +- 185^{21} == +- 67 (mod 281). This approach's flaw is that it is unproven/undetermined whether g is in the orbit of e. I also tried unsuccessfully to use the following: Suppose (p-1) = 2^{B+3} \times (odd r) and g belongs to the exponent G. Then 2^{B+3} divides G. Date: 11/22/2009 at 07:34:09 From: Doctor Jacques Subject: Re: Attacking quad residue eqn when p = 8n+1. Hi Steve, The idea is to work in a subgroup (of the multiplicative group) whose order is a power of 2. Specifically, if p is prime and p-1 = 2^k*q, where q is odd, for any non-zero integer x, x^q has order a power of 2. In this case, we want to solve the congruence: x^2 = a = -7 = 274 (mod 281) We start by computing (except if otherwise stated, everything that follows must be understood as congruences): b = a^35 = 228 We know that the order of b is a power of 2. By repeated squaring, we find: b^2 = 280 (= -1) b^4 = 1 This is to be expected, since we know that b is a quadratic residue. Now, we try to express b as the square root of -1 (b^2). This is where the quadratic non-residue 3 helps. We compute first: g = 3^35 = 60 Because g is a non-residue, we know that g^4 = -1. This means that: (b*g^2)^2 = 1 which implies that b*g^2 = 1 or -1. In this case, we find that b_1 = b*g^2 = -1. As g^4 = -1, we obtain: b*g^6 = 1 a^35*g^6 = 1 Now, we can write: x^2 = a = a*(a^35*g^6) = a^36*g^6 [2] and we can find the solutions: x = (+/-)a^18*g^3 = (+/-)195*162 = (+/-)67 The fact that g is a non-residue ensures that we get an even exponent of g in [2]. This example is not typical, because (p-1) is only divisible by 8 (not by a higher power of 2). The technique can be generalized to other cases. The idea is to find first the highest power of b equal to -1, and to introduce at each step a suitable power of g. For example, if we want to solve: x^2 = a = 8 (mod 97) we start by computing: b = a^3 = 27 and, using the fact that 5 is a non-residue, we also compute: g = 5^3 = 28 We compute the powers of b by repeated squaring: b^2 = 50 b^4 = 75 b^8 = -1 As g^16 = -1, we have: (b*g^2)^8 = 1 and we compute the powers of (b*g^2): b*g^2 = 22 (b*g^2)^2 = -1 To get rid of the -1, we multiply by g^8 inside the brackets: (b*g^10)^2 = 1 Which means that b*g^10 = 1 or -1. In this case, we have b*g^10 = -1. We eliminate the -1 by multiplying by g^16: b*g^26 = 1 = a^3*g^26 And the congruence can now be written as: x^2 = a = a^4*g^26 to give the solution: x = (+/-)a^2*g^13 = (+/-)28 Looking at this, you may get the feeling that some computations are performed more than once. This is indeed true: by keeping track carefully of the operations and re-arranging them a little, it is possible to make the algorithm more efficient. This is known as the Shanks-Tonelli algorithm. You can read something about this on: Shanks-Tonelli Algorithm http://mathforum.org/library/drmath/view/51586.html Wikipedia: Tonelli–Shanks algorithm http://en.wikipedia.org/wiki/Shanks%E2%80%93Tonelli_algorithm Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/