Quadratic residues

Introduction

Quadratic residues can be viewed as a discussion of the feasibility of taking square roots modulo a number. For roots of higher degree, see k-th power residues.

Definition

Euler's criterion

When the modulus is an odd prime, we have the following theorem:

Based on Euler's criterion, we obtain the following corollary:

Legendre symbols

For convenience in the discussion that follows, we introduce the following notation:

That is, for $a$ satisfying $(a,p)=1$:

• $a$ is a quadratic residue modulo $p$ if and only if $\left(\dfrac{a}{p}\right)=1.$
• $a$ is a quadratic non-residue modulo $p$ if and only if $\left(\dfrac{a}{p}\right)=-1.$

The following table lists some values of Legendre symbols (from Wikipedia).

Properties

1. For every integer $a$,

   $$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p.$$

   We further have the following corollaries:

   • $$\left(\dfrac{1}{p}\right)=1.$$
   • $$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\begin{cases} 1, & p\equiv 1\pmod 4,\\ -1, & p\equiv 3\pmod 4. \end{cases}$$

2. $a_1\equiv a_2\pmod p\implies \left(\dfrac{a_1}{p}\right)=\left(\dfrac{a_2}{p}\right).$

3. ( Complete multiplicativity ) For every integer $a_1,a_2$,

   $$\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right).$$

   We have the corollary that for integers $a,b$ with $p\nmid b$,

   $$\left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right).$$
4. $$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases} 1, & p\equiv \pm 1\pmod 8, \\ -1, & p\equiv \pm 3\pmod 8. \\ \end{cases}$$

Based on these properties, if $\left(\dfrac{p}{q}\right)$ can be computed for every pair of odd primes $p$ and $q$, then we can compute the Legendre symbol for every valid case. We now have an elegant theorem that cleverly establishes a connection between $\left(\dfrac{p}{q}\right)$ and $\left(\dfrac{q}{p}\right)$, allowing us to complete the computation using an idea similar to the Euclidean algorithm.

Quadratic reciprocity

There are many proofs¹. One proof is based on the following lemma²:

The following corollaries are easy to obtain:

By the above corollary, proving quadratic reciprocity only requires verifying

Consider the set $S$ of points $(px,qy)$, where $1\leq x\leq \dfrac{q-1}{2},1\leq y\leq \dfrac{p-1}{2}$. Divide it into two parts according to whether $px$ is larger or smaller than $qy$ (clearly $px\neq qy$), and verify the sizes of the three resulting sets.

Quadratic reciprocity can be used not only to determine whether $n$ is a quadratic residue modulo $p$, but also to determine the structure of the moduli for which $n$ is a quadratic residue.

We can also prove conclusions such as “there are infinitely many primes of the form $4k+1$”; these conclusions are actually simple corollaries of Dirichlet's theorem.

Jacobi symbols

Based on quadratic reciprocity, it is natural to consider a generalization of the Legendre symbol:

We can further generalize the modulus to be any integer by defining $\left(\dfrac{a}{-1}\right)$, $\left(\dfrac{a}{0}\right)$, and $\left(\dfrac{a}{2}\right)$; this gives the Kronecker symbol.

Square roots modulo a number

This section discusses algorithms for taking square roots modulo a number. In particular, it mainly introduces the case of a prime modulus. For general moduli, see the discussion of taking higher-degree roots modulo a number.

Algorithms for special cases

For the congruence $x^2\equiv a\pmod p$, where $p$ is an odd prime and $a$ is a quadratic residue, when $p\bmod 4=3$ there is a simpler solution. Consider:

Thus $a^{(p+1)/4}\bmod p$ is a solution.

Atkin's algorithm

Still consider the congruence above. Now $p\bmod 8=5$. Let $b\equiv (2a)^{(p-5)/8}\pmod p$ and $\mathrm{i}\equiv 2ab^2\pmod p$. Then $\mathrm{i}^2\equiv -1\pmod p$, and $ab(\mathrm{i}-1)\bmod p$ is a solution.

Cipolla's algorithm

Cipolla's algorithm solves the congruence $y^2\equiv a\pmod p$, where $p$ is an odd prime and $a$ is a quadratic residue.

This section considers operations in $\mathbf{F}_p\lbrack x\rbrack /(x^2-g)$, where $g \in \mathbf{F}_p$.

The first step of the algorithm is to find an $r$ such that $r^2-a$ is a quadratic non-residue. Of course, such an $r$ cannot be found when $a \equiv 0 \pmod p$, which requires a special case. We discuss only the case $a \not\equiv 0 \pmod p$ below. We can choose a random $r$ and test it; in expectation, $2$ attempts suffice. Then $(r-x)^{\frac{p+1}{2}}\bmod (x^2-(r^2-a))$ is a solution, which can be evaluated by fast exponentiation.

#include <iostream>
#include <random>

long long p, v;  // modulus and the value of r^2 - a

struct Poly {
  long long a, b;

  Poly(long long _a = 0, long long _b = 0) : a(_a), b(_b) {}
};

Poly operator*(const Poly& x, const Poly& y) {
  // Overload multiplication; see the discussion of the operation above
  return Poly((x.a * y.a + v * (x.b * y.b % p)) % p,
              (x.a * y.b + x.b * y.a) % p);
}

// Fast exponentiation for polynomials, used to compute the answer
Poly modpow(Poly a, long long b) {
  Poly res(1, 0);
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

// Ordinary fast exponentiation, used to test for quadratic non-residues
long long modpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

// Used to generate random numbers
std::mt19937 rng(std::random_device{}());

long long cipolla(long long a, long long _p) {
  p = _p;
  if (a == 0)
    return 0;  // Handle the case 0 separately
  else if (modpow(a, (p - 1) / 2) == p - 1)
    return -1;  // A quadratic non-residue; there is no solution
  else {
    // Randomly choose r such that r^2 - a is a quadratic non-residue
    long long r;
    for (r = rng() % p;; r = rng() % p) {
      if (modpow((r * r - a + p) % p, (p - 1) / 2) == p - 1) break;
    }
    v = (r * r - a + p) % p;
    return modpow(Poly(r, 1), (p + 1) / 2).a;  // Compute the result from the conclusion
  }
}

int main() {
  int t, a, p;
  std::cin >> t;
  while (t--) {
    std::cin >> a >> p;
    int ans = cipolla(a, p);
    if (ans == -1)
      std::cout << "Hola!" << std::endl;
    else if (ans == 0)
      std::cout << 0 << std::endl;
    else {
      // The opposite number is the other solution
      int ans2 = (p - ans) % p;
      if (ans2 < ans) std::swap(ans, ans2);
      std::cout << ans << " " << ans2 << std::endl;
    }
  }
  return 0;
}

Bostan–Mori algorithm

This algorithm is based on Cipolla's algorithm. We convert the problem into a constant-coefficient homogeneous linear recurrence and then apply the Bostan–Mori algorithm. Consider another common description of Cipolla's algorithm: $b=x^{\left(p+1\right)/2}\bmod{\left(x^2-tx+a\right)}$ is a solution satisfying $b^2\equiv a\pmod{p}$⁴, where $x^2-tx+a\in \mathbf{F}_p\lbrack x\rbrack$ is an irreducible polynomial. The coefficient $t$ is also chosen randomly. We omit the proof. From the algorithm in the paper by Bostan and Mori⁵, we can see that the problem can be transformed into finding one coefficient of the multiplicative inverse of a formal power series:

and

When $n=0$, clearly $\left\lbrack x^0\right\rbrack\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}=k_0$. This algorithm uses fewer multiplications than Cipolla's algorithm. Other algorithms with fewer multiplications can be found in Müller's article⁶.

Legendre's algorithm

For the congruence $x^2\equiv a\pmod p$, where $p$ is an odd prime and $a$ is a quadratic residue, Legendre's algorithm can be described as finding an $r$ such that $r^2-a$ is a quadratic non-residue, and letting $a_0+a_1x=(r-x)^{\frac{p-1}{2}}\bmod (x^2-a)$. Then $a_0\equiv 0\pmod p$ and $a_1^{-2}\equiv a\pmod p$.

Tonelli–Shanks algorithm

The Tonelli–Shanks algorithm solves the congruence $x^2\equiv a\pmod p$ using discrete logarithms⁷, where $p$ is an odd prime and $a$ is a quadratic residue modulo $p$.

Let $p-1=m2^n$, where $m$ is odd. Again use a random method to find $r\in\mathbf{F}_p$ such that $r$ is a quadratic non-residue. Let $g\equiv r^m\pmod p$ and $b\equiv a^{(m-1)/2}\pmod p$. Then there exists an integer $e\in\lbrace 0,1,2,\dots ,2^n-1\rbrace$ such that $ab^2\equiv g^e\pmod p$. If $a$ is a quadratic residue, then $e$ is even and $\left(abg^{-e/2}\right)^2\equiv a\pmod p$.

The remaining problem is how to compute $e$. Tonelli and Shanks proposed determining one binary digit of $e$ at a time. Write $e$ in binary as $e=e_0+2e_1+4e_2+\cdots$, where $e_k\in\lbrace 0,1\rbrace$. Since $a$ is a quadratic residue, $e_0=0$ initially. We then determine each $e_k$ one bit at a time using the following property:

Here $g^e\equiv ab^2\pmod p$ is known, and $e\bmod 2^k$ can be calculated from the previous digits $e_0,e_1,\cdots,e_{k-1}$. In an implementation, it is enough to maintain the product $g^eg^{-(e\bmod 2^k)}\bmod p$ directly.

Exercises

• Luogu P5491【Template】Quadratic residue
• “Timus 1132” Square Root

References and notes

1. Quadratic residue - Wikipedia
2. Euler's criterion - Wikipedia