Problem 25 - An Introduction to Mathematical Cryptography

Question

Suppose \(n=p q\) with \(p\) and \(q\) both primes. (a) Suppose that \(\operatorname{gcd}(a, p q)=1\). Prove that if the equation \(x^{2} \equiv a(\bmod n)\) has any solutions, then it has four solutions. (b) Suppose you had a machine that could find all four solutions for some given \(a\). How could you use this machine to factor \(n\) ?

Step-by-Step Solution

Answer

There are four solutions by CRT, and gcd computations of differences between solutions can give factors of \( n \).

Step 1: Understand the problem

We are given a composite number \( n = pq \), where both \( p \) and \( q \) are primes. We need to find solutions for the congruence equation \( x^2 \equiv a \pmod{n} \), given that \( \gcd(a, pq) = 1 \).

Step 2: Apply Chinese Remainder Theorem (CRT)

Since \( n = pq \) and \( \gcd(a, n) = 1 \), we can apply the Chinese Remainder Theorem. Solve two congruences: \( x^2 \equiv a \pmod{p} \) and \( x^2 \equiv a \pmod{q} \). Each has two solutions because they are quadratic residues modulo primes.

Step 3: Count solutions

Given that each quadratic congruence \( x^2 \equiv a \pmod{p} \) and \( x^2 \equiv a \pmod{q} \) has two solutions, combine them using CRT to get solutions modulo \( n \). Therefore, the total number of solutions is \( 2 \times 2 = 4 \).

Step 4: Factorization using solutions

If we have a machine that outputs four solutions \( x_1, x_2, x_3, x_4 \) for \( x^2 \equiv a \pmod{n} \), we know that two solutions will be congruent modulo \( p \) and the other two modulo \( q \). Compute \( \gcd(x_1 - x_2, n) \), which gives either \( p \) or \( q \), leading to factorization of \( n \).

Key Concepts

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a powerful tool in number theory that helps solve systems of simultaneous congruences with different moduli. When you have a problem like finding solutions for the equation \( x^2 \equiv a \pmod{n} \), where \( n \) is a product of two different prime numbers, such as \( p \) and \( q \), the CRT is invaluable.
Its strength lies in breaking down complex congruences into simpler problems with smaller moduli. You solve separate congruences for each modulus, for example, \( x^2 \equiv a \pmod{p} \) and \( x^2 \equiv a \pmod{q} \).
The solutions to these simpler problems are then combined into solutions for the original modulus \( n = pq \). This combination gives multiple solutions, in this case, four solutions due to the nature of quadratic congruences. The CRT gives a way to compute these effortlessly, by pairing solutions mod \( p \) with those mod \( q \).
The Chinese Remainder Theorem effectively facilitates finding answers to intricate congruence problems by avenue of reduction to simpler cases, and then cleverly assembling these results to solve the initial query totally.

Quadratic Congruence

A quadratic congruence is an equation of the form \( x^2 \equiv a \pmod{n} \), where you are tasked to find integers \( x \) that satisfy this congruence. For numbers \( n \) that are products of primes, like \( n = pq \), this extends to solving \( x^2 \equiv a \pmod{p} \) and \( x^2 \equiv a \pmod{q} \).
Each of these congruences can be thought of in terms of finding the square root of \( a \) modulo \( p \) and \( q \).
Because \( p \) and \( q \) are primes, these congruences yield two solutions each, just like quadratic equations have two roots.
Thus, when you put these pairs of solutions together using the Chinese Remainder Theorem, they arrange into four solutions for \( x^2 \equiv a \pmod{n} \).
This nature of quadratic congruences fundamentally rests on the properties of modular arithmetic and primes, revealing symmetry and multiplicity in solutions which are harnessed to deeper solve number theory puzzles.

Prime Factorization

Prime factorization involves expressing a number as a product of its prime factors. In the case of the number \( n = pq \), if \( p \) and \( q \) are primes, then \( p \) and \( q \) are its prime factors.
In the given problem, finding the four quadratic solutions and the GCD of their differences enables the discovery of these prime factors.
The method utilizes the insight that pairs of solutions will align with either \( p \) or \( q \), clustering naturally around these factors. By subtracting one solution from another, insights into divisibility by \( p \) or \( q \) arise, effectively offering a window into the number's internal structure.
This factorization allows a breakdown of a number into smaller, simpler components, easing further calculations, especially in cryptographic contexts reliant upon modular arithmetic's complexity and the difficulty of reversing these factorizations.

Greatest Common Divisor

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. It plays a crucial role in various aspects of number theory, particularly in simplifying fractions and solving congruences.
In this exercise, the GCD serves as a diagnostic tool for detecting the prime factors of \( n \).
By computing the GCD between differences of quadratic solutions, like \( \gcd(x_1 - x_2, n) \), you identify either \( p \) or \( q \).
This is due to properties of modular arithmetic and the symmetry of solutions with respect to modulo prime factors, exposing one of the prime divisors of the composite number \( n \).
The method exemplifies using classical number theoretic functions like the GCD to unravel complex structures within numbers, particularly important for cryptography, where deducing these kinds of insights becomes vital.