Agrawal: Finding Quadratic Nonresidues

Let $ p-1=2^\ell s$, $ s$ odd. To find a quadratic non-residue, compute continuously $ -1$, $ (-1)^{1/2}$, $ (-1)^{1/4}$, $ \dots$, $ (-1)^{1/2^{\ell-1}}$. One can quickly compute $ (-1)^{1/2}$ from an algorithm due to Schoof, but one gets stuck at $ (-1)^{1/8}$.

The idea: in primality testing, we want to know if $ \mathbb{Z}/n\mathbb{Z}$ is a field, so we embed it into $ (\mathbb{Z}/n\mathbb{Z})[X]/(X^r-1)$; this ring has enough structure to pull out a nice algorithm. Assume that $ \ell \geq 2$, and we try only to compute $ \sqrt{-1}$. Now we embed in $ \mathbb{F}_p[X]/(X^2+1)$. Consider $ g(X)=(1-X)^s$. Observe that $ (g(X))^{2^\ell}=1$ in $ \mathbb{F}_p[X]/(X^2+1)$, so $ g(X)$ is a $ 2^\ell$th root of unity.

Assume that $ \ell=2$. In this case, $ g(X)$ is a fourth root of unity. But $ X$ is also a fourth root, so $ g(X)=X^k \pmod{X-\omega}$ where $ \omega$ is the `real' fourth root of unity. Consider $ g(X) \bmod (X^2+1)$: observe that $ g(X) \neq X^k \pmod{X^2+1}$ for any $ k$. For suppose

$\displaystyle (1-X)^s \equiv X^k \pmod{X^2+1}; $

then

$\displaystyle (1-1/X)^s = 1/X^k \pmod{1/X^2+1}, $

so

$\displaystyle (1-X)^s=-(X^s/X^k) \pmod{X^2+1}, $

hence $ -(X^s/X^k) =X^k \pmod{X^2+1}$, a contradiction because $ s$ is odd. So compute $ \gcd(g(X)-X^k,X^2+1)$, for each $ k$, one of them will factor $ X^2+1$.

If $ \ell>2$, then you cannot argue $ g(X) \equiv X^k \pmod{X-\omega}$. If $ \ell>2$, then it is possible that $ g(X)$ is an eighth root or a sixteenth root or so on. Suppose that $ g(X)$ modulo $ X^2+1$ is an eighth root, for example. Then $ g(X^2)=(1-X^2)^s \equiv X^k \pmod{X-\zeta}$ for some factor $ X-\zeta$ of $ X^4+1$ and $ k$ odd. But $ (1-X^2)^s$ is even, so it cannot be an odd power, so $ \gcd((1-X^2)^s-X^k,X^4+1)$ will give either a linear factor (in which case we are done) or a product of quadratic factors $ (X-\zeta^2)(X+\zeta^2)$ or the products similar to $ (X-\zeta)(X-\zeta^3)$ and $ (X-\zeta)(X+\zeta^3)$.

Let $ h(X)$ be a quadratic factor of $ X^4+1$. Now if $ (1-X)^s \not\equiv X^k \pmod{h(X)}$, then $ h(X)$ can be factored and we are done. Suppose

$\displaystyle (1-X)^s \equiv X^k \pmod{(X-\zeta)(X-\zeta^3)} $

and

$\displaystyle (1-X)^s \equiv X^{k'} \pmod{(X+\zeta)(X+\zeta^3)}. $

If you replace $ X$ by $ X^3$, then you get

$\displaystyle (1-X^3)^s=X^{3k} \pmod{(X^3-\zeta)(X^3-\zeta^3)} $

so

$\displaystyle (1-X^3)^s \equiv X^{3k}=(1-X)^{3s} \pmod{(X-\zeta)(X-\zeta^3)}. $

That means that $ 3$ is introspective for $ (1-X)^s$. The same argument applies to the other congruence, so one obtains that $ 3$ is introspective for $ (1-X)^s \bmod X^4+1$.

Now try all over again now with $ X-a$ replacing $ 1-X$; the bad case will be when we have $ 3$ is introspective for $ (a-X)^s \bmod X^4+1$ for a large number of $ a$. Here we get stuck, but this should be impossible.

Remarks.

  1. There was a solution due to Lehmer which says for any fixed $ \ell$ 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 $ s>1$ means that the same techniques as in the primality test do not seem to apply. Can you solve the problem if $ s=3$, or for other small $ s$? (Lenstra) The case of a Fermat prime is trivial ($ 3$ is a nonresidue, and there probably aren't any above $ 65537$). (Lenstra, Elkies) It seems as though if $ s$ is bounded, there are only a finite number of problematic $ a$. For example, $ (a-X^3)^s \equiv (a-X)^3 \pmod{h(X)}$ does not hold for `many' $ a$ (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 $ 1$)? (Elkies) Yes, but we need to solve this problem first. (Agrawal)
  5. How many values of $ a$ do you need? (Voloch) It seems unlikely you can generate the whole group with the $ (X-a)^s$ without the GRH. (Bernstein)



Back to the main index for Future directions in algorithmic number theory.