Quadratic Residuosity with Legendre and Jacobi Symbols

In our last lesson, we focused on the computational engine of public-key cryptography: the square-and-multiply algorithm for modular exponentiation. We analyzed its efficiency, which is what makes systems like RSA practical. Today, we shift our focus to another fundamental question in number theory with deep cryptographic implications: how to determine if a number has a square root modulo another number.

This question, known as determining quadratic residuosity, is central to several cryptographic protocols, including the Goldwasser-Micali cryptosystem and some zero-knowledge proofs. Our goal in this lesson is to master the tools for answering this question efficiently: the Legendre and Jacobi symbols. We will define these symbols, understand their properties, and, most importantly, develop an efficient algorithm for their computation that leverages your computer science background.

Quadratic Residues and the Legendre Symbol

The core problem is to determine whether the congruence $x^{2} \equiv a (mod p)$ has a solution, where $p$ is an odd prime.

If a solution exists and $a \neq \equiv 0 (mod p)$ , we say that $a$ is a quadratic residue modulo $p$ .
If no solution exists, we say $a$ is a quadratic non-residue modulo $p$ .

To formalize this, mathematicians introduced the Legendre symbol. The following video provides a concise definition and a clear example.

Number Theory | The Legendre Symbol and Euler's Criterion

This video by Michael Penn introduces the concept of quadratic residues and defines the Legendre symbol as a way to classify them.

Watch the first segment of the video, from the beginning until the example with p=7. This will give you the formal definition of the Legendre symbol, denoted (\frac{a}{p}), and its values (1, -1, or 0).

As the video explains, the Legendre symbol $(\frac{a}{p})$ is defined as:

(\frac{a}{p}) = ⎩ ⎨ ⎧ 1 - 1 0 if a is a quadratic residue modulo p if a is a quadratic non-residue modulo p if p ∣ a

Euler's Criterion

A first, powerful method for calculating the Legendre symbol connects directly to our previous lesson on modular exponentiation. Euler's criterion states that for an odd prime $p$ and an integer $a$ such that $p ∤ a$ :

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)

This is a remarkable result. It transforms the problem of finding a square root into a modular exponentiation problem, which we know how to solve efficiently using the square-and-multiply algorithm.

[PDF] 1.1 Legendre Symbol - CSE IIT KGP

These lecture notes from IIT Kharagpur provide a formal statement of the key properties of the Legendre symbol.

Please read the definition and the list of properties in this document. Start at the definition of the Legendre symbol. Then, review the list of properties in Proposition 1, paying special attention to property 3, which is Euler's Criterion.

The proof of Euler's criterion is elegant and reinforces concepts like Fermat's Little Theorem. You can watch the proof in the same Michael Penn video from Euler's Criterion if you are interested.

A More Efficient Path: The Law of Quadratic Reciprocity

While Euler's criterion provides a computational path, a deeper structure discovered by Gauss provides an even more efficient method, especially for calculations by hand or for building recursive algorithms. This structure is captured by the Law of Quadratic Reciprocity.

This law and its supplements allow us to "flip" and reduce Legendre symbols in a way that is reminiscent of the Euclidean algorithm for finding the greatest common divisor.

The main results are:

Law of Quadratic Reciprocity: For distinct odd primes $p$ and $q$ :
$(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \frac{q - 1}{2}}$
This means $(\frac{p}{q}) = (\frac{q}{p})$ unless both $p$ and $q$ are of the form $4 k + 3$ , in which case $(\frac{p}{q}) = - (\frac{q}{p})$ .
First Supplement:
$(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}} = {1 - 1 if p \equiv 1 (mod 4) if p \equiv 3 (mod 4)$
Second Supplement:
$(\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}} = {1 - 1 if p \equiv 1 or 7 (mod 8) if p \equiv 3 or 5 (mod 8)$

Using these rules, along with the multiplicative property $(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})$ , we can break down any Legendre symbol into smaller, easily computable pieces. For example, to compute $(\frac{29}{53})$ :

$29$ and $53$ are both prime. Since $53 \equiv 1 (mod 4)$ , we can flip the symbol without a sign change: $(\frac{29}{53}) = (\frac{53}{29})$ .
Reduce the numerator modulo the denominator: $53 \equiv 24 (mod 29)$ , so we have $(\frac{24}{29})$ .
Use multiplicativity: $(\frac{24}{29}) = (\frac{8 \cdot 3}{29}) = (\frac{2 ^{3}}{29}) = (\frac{2 ^{2}}{29}) (\frac{2}{29}) = 1 \cdot (\frac{2}{29})$ .
Apply the second supplement: Since $29 \equiv 5 (mod 8)$ , $(\frac{2}{29}) = - 1$ .
Therefore, $(\frac{29}{53}) = - 1$ , and 29 is a quadratic non-residue modulo 53.

Notice a potential bottleneck: in the step $(\frac{24}{29})$ , we had to find the prime factorization of 24. For large numbers, this factorization step is computationally very expensive. This is the motivation for our next tool.

The Jacobi Symbol: A Computational Generalization

The Jacobi symbol, also denoted $(\frac{a}{n})$ , generalizes the Legendre symbol to odd composite denominators $n$ . Its primary purpose is not to test for quadratic residuosity directly, but to serve as an efficient computational tool.

Introduction to number theory lecture 35 Jacobi symbol

This lecture provides a clear and rigorous introduction to the Jacobi symbol, highlighting its computational advantages and a crucial point of difference from the Legendre symbol.

First, watch the introduction from the definition to see how the Jacobi symbol is defined based on the prime factorization of the denominator. Next, from the properties, note that all the key properties of the Legendre symbol, including the Law of Quadratic Reciprocity, carry over. Then, watch the critical segment from the big warning. This explains the most important difference between the two symbols. Finally, see from the computational advantage how the Jacobi symbol allows for a fast, Euclid-like algorithm.

Let's summarize the key points from the video.

Definition: If $n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{m}^{k_{m}}$ is the prime factorization of an odd integer $n$ , the Jacobi symbol is defined as:
$(\frac{a}{n}) = (\frac{a}{p _{1}})^{k_{1}} (\frac{a}{p _{2}})^{k_{2}} \dots (\frac{a}{p _{m}})^{k_{m}}$
where the symbols on the right are Legendre symbols.

The Crucial Warning:
As emphasized in the video, if $n$ is composite, $(\frac{a}{n}) = 1$ does not imply that $a$ is a quadratic residue modulo $n$ . For example, $(\frac{2}{15}) = (\frac{2}{3}) (\frac{2}{5}) = (- 1) (- 1) = 1$ . However, $x^{2} \equiv 2 (mod 15)$ has no solution because it would require solutions modulo 3 and 5, and $x^{2} \equiv 2 (mod 3)$ has no solution.
However, if $(\frac{a}{n}) = - 1$ , we can definitively conclude that $a$ is a quadratic non-residue modulo $n$ .

The Computational Advantage:
The power of the Jacobi symbol is that all the reciprocity laws hold. This means we can use the "flip and reduce" strategy without ever needing to factor the numerator. This leads to an algorithm with a complexity similar to the Euclidean algorithm.

The following document provides a side-by-side comparison that makes this advantage crystal clear.

[PDF] NUMBER THEORY NOTES ON JACOBI SYMBOLS Vanderbilt ...

This document from Vanderbilt University demonstrates the power of the Jacobi symbol with a concrete example.

Read the section titled Example near the end of the document. It computes (\frac{713}{1009}) using two methods: Method 1 (Legendre) and Method 2 (Jacobi). Notice how Method 1 requires factoring 713 = 23 \cdot 31, while Method 2 proceeds directly by flipping (\frac{1009}{713}) without needing to know the factors of 713.

An Efficient Algorithm for the Jacobi Symbol

We can now formalize the process into an algorithm. This algorithm computes $(\frac{a}{n})$ efficiently by repeatedly reducing the numerator, factoring out powers of 2, and applying the reciprocity law to flip the numerator and denominator.

[PDF] 1.1 Legendre Symbol - CSE IIT KGP

These notes formalize the computational process into a concrete algorithm and analyze its efficiency.

Please read the entire section 1.4 Computation of Jacobi Symbol. It begins with a list of rules for the computation. Then, study the pseudocode for the jacobi(a, n) function. Finally, read the complexity analysis which shows that the number of iterations is O(\log n), just like the Euclidean algorithm.

The jacobi(a, n) algorithm presented is a beautiful piece of computational number theory. It elegantly combines modular arithmetic and the reciprocity laws into a tight, efficient loop that avoids the hard problem of integer factorization. Understanding this algorithm is the main goal of this lesson.

Conclusion

In this lesson, we have built the machinery to efficiently determine quadratic residuosity.

Key Takeaways:

Quadratic Residues: An integer $a$ is a quadratic residue modulo $p$ if $x^{2} \equiv a (mod p)$ has a solution.
Legendre Symbol $(\frac{a}{p})$ : A function that is +1 for quadratic residues, -1 for non-residues, and 0 for multiples of $p$ . It is defined only for prime denominators.
Euler's Criterion: Connects the Legendre symbol to modular exponentiation: $(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)$ .
Law of Quadratic Reciprocity: A set of rules that allow for the efficient, recursive computation of the Legendre symbol.
Jacobi Symbol $(\frac{a}{n})$ : A generalization to odd composite denominators $n$ . Its main purpose is computational efficiency.
Critical Distinction: $(\frac{a}{n}) = 1$ does not imply $a$ is a quadratic residue modulo $n$ . However, $(\frac{a}{n}) = - 1$ does imply $a$ is a non-residue.
Efficient Algorithm: By using the reciprocity laws for the Jacobi symbol, we can compute it in logarithmic time without factoring the numerator, much like the Euclidean algorithm for GCD.

We have seen how the Law of Quadratic Reciprocity enables this efficient computation, but we have taken the law itself as given. In our next lesson, we will delve into the "why". We will formally state and then prove this cornerstone theorem of number theory, exploring one of its most elegant proofs.

Recommended resources