Attacking quad residue eqn when p = 8n+1.
zugzwang
Number Theory. Chapter 10 introduces Legendre and Jacobi symbols,
proves the quadratic reciprocity law, and provides attack methods for
quadratic congruences of prime moduli (among other things). The
problem is presented verbatim and then interpreted, to facilitate
snaring the authors' insights. My flawed approach, which might be
repairable, is also included. Request help, thanks.
Verbatim:
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).
Interpretation:
The book was written in the 1930's, which predates computers. It
references, for example, "A Photo Electric Number Sieve", so computer/
calculator use in the (intended) method should be "light." Just
before presenting this problem, the chapter concludes with sections 18
and 19. Section 18 discusses solving quadratic congruences for prime
moduli congruent to 3,5, or 7 (mod 8). In this situation, one of
(p-1)/2, (p-1)/4 will (critically) be odd. Section 19 converts x^2 ==
a (mod p) to a + py = x^2 and then attacks "excluding" _virtually_ all
values of y between 0 and (p-1)/4.
The exclusion method is presented in a separate post-chapter
exercise. Based on that + the verbatim problem, I suspect that the
authors' intend subtly altering the method of section 18.
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.
Chip Eastham
Check out the Shanks-Tonelli algorithm:
http://en.wikipedia.org/wiki/Shanks%E2%80%93Tonelli_algorithm
regards, chip
zugzwang
Directly on point, thanks. If I have trouble proving that the
procedure is rigorous, I will re-post.