Agrawal: Finding Quadratic Nonresidues
, odd. To find a quadratic non-residue, compute continuously ,
. One can quickly compute
from an algorithm due to Schoof, but one gets stuck at
The idea: in primality testing, we want to know if
is a field, so we embed it into
; this ring has enough structure to pull out a nice algorithm. Assume that
, and we try only to compute . Now we embed in
. Observe that
, so is a th root of unity.
Assume that . In this case, is a fourth root of unity. But is also a fourth root, so
where is the `real' fourth root of unity. Consider
: observe that
for any . For suppose
, a contradiction because is odd. So compute
, for each , one of them will factor .
If , then you cannot argue
. If , then it is possible that is an eighth root or a sixteenth root or so on. Suppose that modulo is an eighth root, for example. Then
for some factor of and odd. But is even, so it cannot be an odd power, so
will give either a linear factor (in which case we are done) or a product of quadratic factors
or the products similar to
Let be a quadratic factor of . Now if
, then can be factored and we are done. Suppose
If you replace by , then you get
That means that is introspective for . The same argument applies to the other congruence, so one obtains that is introspective for
Now try all over again now with replacing ; the bad case will be when we have is introspective for
for a large number of . Here we get stuck, but this should be impossible.
- There was a solution due to Lehmer which says for any fixed that you can solve this problem? (Cohen) But that assumes the existence of a nonresidue to begin with, which is exactly our problem. (Bernstein) But also this doesn't seem to scale well. (Cohen) There is a strategy to deal with this, and we always work modulo a degree four polynomial. (Agrawal)
- The fact that means that the same techniques as in the primality test do not seem to apply. Can you solve the problem if , or for other small ? (Lenstra) The case of a Fermat prime is trivial ( is a nonresidue, and there probably aren't any above ). (Lenstra, Elkies) It seems as though if is bounded, there are only a finite number of problematic . For example,
does not hold for `many' (Pomerance).
- One strategy to solve this problem: translate this problem into rings and stare at it. (Lenstra)
- Is there a strategy to deal with cases beyond eighth roots (where we have the special situation that every odd integer has square )? (Elkies) Yes, but we need to solve this problem first. (Agrawal)
- How many values of do you need? (Voloch) It seems unlikely you can generate the whole group with the without the GRH. (Bernstein)
Back to the
for Future directions in algorithmic number theory.