Two completely different “modulo” rules are about to coexist
One rule controls our positions: powers at degree N wrap because xᴺ=−1. A second rule controls our coefficient values: an integer is represented by its remainder modulo a prime q. They are completely independent boundaries! A coefficient can remain safely at position 17 while its numeric value is reduced modulo q, or a term can wrap to a totally new position while its coefficient also receives the negacyclic sign change.
Let's formalize the fixed-length position rule we already know
Chapter 2 introduced N coefficient positions and the substitution xᴺ=−1. Formal algebra writes the exact same rule as "polynomials modulo xᴺ+1". No new routing behavior is being introduced here; the notation simply names the structure we already used in our wrap proof.
Large integers use several modular views
Hardware multipliers operate much more efficiently when working below a chosen prime. Instead of storing one massive coefficient directly, the residue number system stores its remainder modulo several pairwise-compatible primes.
Worked example
A toy residue view
The integer 23 appears as 2 modulo 7 and 3 modulo 5. Search the integers 0 through 34 and only 23 has both of those properties. The pair (2,3), together with those specific moduli, perfectly identifies 23 inside that 35-value window. After 35 the pattern repeats, so a bounded range is part of the contract. These are two views of one single value—not two coordinates and definitely not two scores.
value = 23
moduli = [7, 5]
limbs = [value % q for q in moduli] # [2, 3]
candidates = [x for x in range(35)
if all(x % q == limb
for q, limb in zip(moduli, limbs))]
assert candidates == [23]Why must the residue primes be compatible?
If two moduli share factors, their remainder patterns repeat much sooner and they don't contribute their full combined range. Pairwise coprime moduli let the joint pattern cleanly span the massive product q₀q₁⋯. Production constants are carefully chosen together with transform and security requirements; “just pick any primes” is a terrible implementation rule.
Check your understanding
What exactly do three residue limbs represent?
Section summary
- xᴺ+1 notation simply names the familiar negacyclic boundary.
- Residue limbs split a large numeric range across multiple primes.
- Limbs absolutely do not split logical messages.
Repository layer · second pass
Why view one large coefficient through several small moduli?
Residue number representation stores the same coefficient modulo several pairwise-coprime primes. Each limb is an independent view, not a different coordinate or ciphertext component. Together, the limbs represent a range roughly equal to the product of their moduli.
Arithmetic can proceed independently per limb, creating parallel hardware lanes. Reconstruction or basis conversion later reconnects the views. Keep three axes separate: coefficient index, residue limb, and ciphertext component.
Reasoning chain
- 1
Choose pairwise-coprime moduli.
- 2
Reduce the same integer into every limb.
- 3
Perform matching modular operations per limb.
- 4
Reconstruct only when the combined integer view is needed.
- 5
Track centered versus unsigned interpretation.
Worked trace
Three views of −5
- Use moduli 7,11,13.
- −5 appears as residues 2,6,8.
- Each limb looks positive in canonical form.
- Centered interpretation recovers a negative representative.
Result. Residues are coordinated views of one value.
Executable lens · Python
Make the hidden state visible
value=-5
moduli=[7,11,13]
residues=[value % q for q in moduli]
assert residues == [2,6,8]Retype this example, predict each intermediate value, and then change one input that touches a boundary.
Misconception clinic
Tempting mistakes
- Treating limbs as extra embedding positions.
- Mixing residues from different coefficients or modulus sets.
Retrieval and transfer
Close the book first
- Compute residues of 100 under three primes.
- Explain why moduli must be pairwise coprime for full CRT range.
- Draw the component×limb×coefficient tensor.