TAOCP 4.5.4 Exercise 35

Let N = pq, \qquad p \equiv 3 \pmod 8, \qquad q \equiv 7 \pmod 8 be the product of two distinct odd primes.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.4: Factoring into Primes

Exercise 35. ▶ [M25] (H. C. Williams, 1979.) Let $N$ be the product of two primes $p$ and $q$, where $p \bmod 8 = 3$ and $q \bmod 8 = 7$. Prove that the Jacobi symbol satisfies $\left(\frac{-1}{N}\right) = -\left(\frac{2}{N}\right)$, and use this property to design an encoding/decoding scheme analogous to Rabin's SQRT box but with no ambiguity of messages.

Verified: yes
Solve time: 9m49s

Corrected Solution

Let

$$ N = pq, \qquad p \equiv 3 \pmod 8, \qquad q \equiv 7 \pmod 8 $$

be the product of two distinct odd primes. We first verify the Jacobi-symbol identity.

Part 1: Proof that $\displaystyle \left(\frac{-1}{N}\right) = -\left(\frac{2}{N}\right)$

By multiplicativity of the Jacobi symbol:

$$ \left(\frac{-1}{N}\right) = \left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right), \qquad \left(\frac{2}{N}\right) = \left(\frac{2}{p}\right)\left(\frac{2}{q}\right). $$

For an odd prime $r$, we have the standard formulas:

$$ \left(\frac{-1}{r}\right) = (-1)^{(r-1)/2}, \qquad \left(\frac{2}{r}\right) = (-1)^{(r^2-1)/8}. $$

Since $p \equiv 3 \pmod 8$:

$$ \left(\frac{-1}{p}\right) = (-1)^{(3-1)/2} = (-1)^1 = -1, \qquad \left(\frac{2}{p}\right) = (-1)^{(3^2-1)/8} = (-1)^{(9-1)/8} = (-1)^1 = -1. $$

Since $q \equiv 7 \pmod 8$:

$$ \left(\frac{-1}{q}\right) = (-1)^{(7-1)/2} = (-1)^3 = -1, \qquad \left(\frac{2}{q}\right) = (-1)^{(7^2-1)/8} = (-1)^{(49-1)/8} = (-1)^6 = 1. $$

Hence:

$$ \left(\frac{-1}{N}\right) = (-1)(-1) = 1, \qquad \left(\frac{2}{N}\right) = (-1)(1) = -1. $$

Thus:

$$ \boxed{\left(\frac{-1}{N}\right) = -\left(\frac{2}{N}\right)}. $$

Part 2: Construction of an ambiguity-free Rabin/Williams encoding scheme

Rabin's original encryption $E(m) = m^2 \pmod N$ is ambiguous because each quadratic residue modulo $N$ has four square roots:

$$ x, -x, x', -x', $$

where $x'$ differs from $x$ by sign modulo exactly one of the primes. To remove ambiguity, we exploit the special congruence conditions:

$$ \left(\frac{-1}{N}\right) = 1, \qquad \left(\frac{2}{N}\right) = -1. $$

These provide two independent binary invariants to distinguish the four roots uniquely.

Step 2.1: Quadratic residue and Jacobi symbol

Let $y \equiv x^2 \pmod N$, with $\gcd(x,N)=1$. The four roots of $y$ modulo $N$ are:

$$ {\pm x, \pm x'}. $$

Compute the Jacobi symbol:

$$ \left(\frac{r}{N}\right) = \left(\frac{r}{p}\right)\left(\frac{r}{q}\right). $$

Since $\left(\frac{-1}{N}\right) = 1$, we have:

$$ \left(\frac{-x}{N}\right) = \left(\frac{-1}{N}\right)\left(\frac{x}{N}\right) = \left(\frac{x}{N}\right), $$

so $x$ and $-x$ have the same Jacobi symbol. Similarly, $x'$ and $-x'$ share a Jacobi symbol, which is opposite to that of $x$:

$$ \left(\frac{x'}{N}\right) = -\left(\frac{x}{N}\right). $$

Thus, the Jacobi symbol splits the four roots into two pairs: one pair with symbol $+1$ and one with symbol $-1$. We select the pair with Jacobi symbol $+1$ as the canonical candidate set.

Step 2.2: Distinguishing roots within the pair

Let $r \in {\pm x}$ be a candidate with $\left(\frac{r}{N}\right) = 1$. Define the mapping:

$$ r \mapsto s \equiv r \pmod 2. $$

Because $\left(\frac{2}{N}\right) = -1$, multiplication by 2 flips the Jacobi symbol:

$$ \left(\frac{2r}{N}\right) = \left(\frac{2}{N}\right)\left(\frac{r}{N}\right) = -1. $$

Therefore, exactly one of $r$ and $2r$ has Jacobi symbol $+1$. Among the pair ${\pm x}$, exactly one satisfies $r \equiv 1 \pmod 2$. Using the parity of $r$ (or another small fixed criterion, e.g., $r \bmod 4$) in combination with the Jacobi symbol, we select a canonical representative. Specifically, define the canonical square root as:

$$ \text{root}(y) = \text{the element of }{\pm x}\text{ that is odd modulo 2}. $$

This criterion distinguishes $x$ from $-x$ unambiguously.

Step 2.3: Encoding

Define the message space as:

$$ \mathcal{M} = { m \pmod N : \gcd(m,N)=1}. $$

The encryption of $m \in \mathcal{M}$ is:

$$ E(m) \equiv m^2 \pmod N. $$

The ciphertext consists of $c = m^2 \pmod N$ without additional bits, because the canonical root selection criterion ensures unique decoding.

Step 2.4: Decoding

To decrypt $c \equiv m^2 \pmod N$:

  1. Compute the four roots ${\pm r, \pm r'}$ modulo $N$ using the Chinese remainder theorem.
  2. Compute the Jacobi symbol $\left(\frac{r}{N}\right)$ for each root. Select the pair with symbol $+1$.
  3. Within that pair, select the canonical root according to parity (or another fixed property, e.g., the smaller of the two modulo $N$ if needed). This uniquely recovers $m$.

Thus every ciphertext corresponds to exactly one message, resolving the original ambiguity.

Step 3: Summary

  • The congruences $p \equiv 3 \pmod 8, q \equiv 7 \pmod 8$ guarantee:

$$ \left(\frac{-1}{N}\right) = 1, \qquad \left(\frac{2}{N}\right) = -1. $$

  • This ensures that $x$ and $-x$ have the same Jacobi symbol, and multiplication by 2 flips the Jacobi symbol.
  • Combining Jacobi-symbol selection and a fixed canonical criterion (such as parity) yields a one-to-one correspondence between messages and ciphertexts.
  • The scheme is an ambiguity-free analogue of Rabin's SQRT box, as required by the exercise.

$\square$