Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 37 ยท Quadratic Residues

Legendre and Jacobi Symbols

Compute Legendre and Jacobi symbols with quadratic reciprocity, without factoring, and use them in the Solovay-Strassen primality test.

Euler's criterion decides whether a is a square modulo a prime p, but it needs a modular exponentiation. Gauss found something far faster and more beautiful: a reciprocity law that lets you flip the symbol, reduce, and repeat, exactly like the Euclidean algorithm. He called it the "golden theorem" and published six proofs.

This lesson introduces the Legendre symbol (a/p), states the laws it obeys, extends it to composite bottoms with the Jacobi symbol, and shows an algorithm that never factors anything. We finish with the Solovay-Strassen primality test, a cousin of Miller-Rabin.

The Legendre symbol

For an odd prime p:

(a/p) = 0 if p | a, +1 if a is a quadratic residue, and -1 if it is a non-residue.

By Euler's criterion, (a/p) โ‰ก a^((p-1)/2) (mod p). Immediate consequences:

  • Multiplicative: (ab/p) = (a/p)(b/p).
  • Periodic: (a/p) depends only on a mod p.
  • First supplement: (-1/p) = (-1)^((p-1)/2), so -1 is a residue iff p โ‰ก 1 (mod 4).
  • Second supplement: (2/p) = (-1)^((pยฒ-1)/8), so 2 is a residue iff p โ‰ก ยฑ1 (mod 8).
Python Checking the supplementary laws

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quadratic reciprocity

For distinct odd primes p and q:

(p/q)ยท(q/p) = (-1)^(((p-1)/2)ยท((q-1)/2)).

In words: the two symbols are equal unless both primes are 3 (mod 4), in which case they are opposite. This remarkable link between "is p a square mod q" and "is q a square mod p" turns a computation modulo a large prime into one modulo a small one.

Python Verifying reciprocity numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Jacobi symbol

Reciprocity is awkward if the numbers are not prime, because the Legendre symbol needs a prime on the bottom. The Jacobi symbol (a/n) for odd n = pโ‚^eโ‚ ... pโ‚–^eโ‚– is defined by

(a/n) = (a/pโ‚)^eโ‚ ยท ... ยท (a/pโ‚–)^eโ‚–.

It has the same properties: multiplicative in both arguments, periodic in a, and obeys both supplements and reciprocity for coprime odd m, n. But watch out: (a/n) = 1 does not mean a is a square modulo n (for composite n). (a/n) = -1 does imply that a is a non-residue.

The beauty is that this definition can be computed without factoring n, by reciprocity.

Python Jacobi symbol by reciprocity (no factoring)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop looks like Euclid's algorithm: reduce, swap, reduce. Therefore the cost is O(logยฒ n) bit operations, much better than a modular exponentiation. Our version agrees with SymPy's jacobi_symbol on all tested inputs.

The caveat in action: (2/15) = (2/3)(2/5) = (-1)(-1) = +1, yet 2 is not a square modulo 15 because it isn't a square modulo 3.

Python Jacobi = +1 does not mean square

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four numbers have symbol +1 but only two (1 and 4) are squares; the other two (2 and 8) fool the symbol.

Solovay-Strassen primality test

For prime n the Jacobi symbol (a/n) equals a^((n-1)/2) mod n (Euler's criterion). For an odd composite n this fails for at least half of the bases a. The Solovay-Strassen test picks random a and checks a^((n-1)/2) โ‰ก (a/n) (mod n).

Python Solovay-Strassen test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Unlike plain Fermat, Solovay-Strassen exposes Carmichael numbers, because the failure rate for composites is at least 1/2 per round. Miller-Rabin is stronger (at most 1/4 liars) and cheaper, so it won in practice.

flowchart TD
    S["jacobi(a, n)"] --> M["a = a mod n"]
    M --> T["remove factors of 2 (supplement)"]
    T --> F["swap a and n (reciprocity, sign flip if both are 3 mod 4)"]
    F --> M

The loop at the heart of the Jacobi algorithm.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. For which primes p is -1 a quadratic residue?

    (-1/p) = (-1)^((p-1)/2), which is +1 exactly when (p-1)/2 is even, i.e. p โ‰ก 1 mod 4.
  2. 2. When do (p/q) and (q/p) have opposite signs?

    The exponent ((p-1)/2)((q-1)/2) is odd exactly when both are 3 mod 4.
  3. 3. If the Jacobi symbol (a/n) = +1 for composite n, then:

    Two non-residue factors multiply to +1, as in (2/15) = +1 but 2 is not a square mod 15.
  4. 4. What is (2/17)?

    17 โ‰ก 1 mod 8, so 2 is a residue: 6*6 = 36 = 2 mod 17.

Summary

  • The Legendre symbol (a/p) is +1, -1 or 0 and equals a^((p-1)/2) mod p.
  • Supplements: -1 is a residue iff p โ‰ก 1 (mod 4); 2 iff p โ‰ก ยฑ1 (mod 8).
  • Reciprocity: (p/q)(q/p) = (-1)^(((p-1)/2)((q-1)/2)).
  • The Jacobi symbol extends this to odd composites and is computed Euclid-style, without factoring.
  • (a/n) = -1 proves a non-residue; +1 for composite n does not prove a residue.
  • Solovay-Strassen compares the Jacobi symbol with Euler's criterion to test primality.

Next: Tonelli-Shanks Square Roots