Associated Topics || Dr. Math Home || Search Dr. Math

Date: 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
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/

Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search