Quadratic Residue Equations

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. 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/