Let , 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 . Consider . Observe that in , 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

then

so

hence , 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 and .

Let be a quadratic factor of . Now if , then can be factored and we are done. Suppose

and

If you replace by , then you get

so

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.

Remarks.

1. 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)
2. 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).
3. One strategy to solve this problem: translate this problem into rings and stare at it. (Lenstra)
4. 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)
5. 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 main index for Future directions in algorithmic number theory.