Rings: Addition and Multiplication

Complex numbers were invented because x² = -1 had no solution in R. But there is no magic here - it is a quotient ring: R[x]/(x²+1). The ring literally manufactures new numbers from old ones by adding a single equation. AES-256, RSA, CRYSTALS-Kyber (the NIST 2024 post-quantum standard) - all operate inside rings. Abstract algebra guards the internet.

• **AES-256**: every encryption operation is multiplication in GF(2⁸) = F₂[x]/(x⁸+x⁴+x³+x+1). A polynomial ring over GF(2) with 256 elements - every byte of AES lives here.
• **RSA / Diffie-Hellman / DSA**: the residue ring Z/nZ is the base structure. The security of RSA rests on the hardness of finding polynomial roots in Z/nZ.
• **CRYSTALS-Kyber (post-quantum cryptography)**: operates in Z[x]/(xⁿ+1). NTT - the ring analogue of FFT - accelerates polynomial multiplication from O(n²) to O(n log n).
• **TFHE homomorphic encryption**: computations directly on encrypted data in Z[x]/(xⁿ+1). The foundation of cloud computing without data leakage.

Предварительные знания

• Homomorphisms and Isomorphisms

Ring Axioms: Two Operations

A **group** has one operation. A **ring** has two, with the second distributing over the first. That small addition changes everything: zero divisors, nilpotent elements, and ideals appear - objects that simply do not exist in the domain of groups. Formally, a **ring** is a set R with operations (+, x) where (R, +) is an abelian group, (R, x) is an associative semigroup, and multiplication distributes over addition from both sides.

**Three degrees of freedom absent from groups:** zero divisors (2x3=0 in Z/6Z), nilpotent elements (a with a^n=0), and ideals (substructures that absorb multiplication). Ideals build quotient rings - and that is precisely how R[x]/(x²+1) becomes the field of complex numbers.

Rings Around Us: From Z/nZ to GF(2⁸)

Rings are not abstraction for its own sake. Z/nZ underlies RSA and Diffie-Hellman. GF(2⁸) = F₂[x]/(x⁸+x⁴+x³+x+1) is the field in which every AES-256 operation runs. The ring Z[x]/(xⁿ+1) is used in CRYSTALS-Kyber - the NIST 2024 post-quantum standard. The hierarchy matters.

**Zero divisors break familiar algebra.** In Z one can cancel: if 2a = 2b then a = b. In Z₆ this fails: 2x1 = 2 and 2x4 = 8 = 2 (mod 6), but 1 ≠ 4. In cryptography this is critical: Cloudflare once found a bug in a GF(2⁸) multiplication implementation that produced a complete break of AES. Always verify an element is not a zero divisor before canceling.

Ideals and Quotient Rings: Where Complex Numbers Come From

An **ideal** I of a ring R is a subgroup of (R, +) that absorbs multiplication: for any r in R and a in I, both ra and ar lie in I. Ideals are the analogue of normal subgroups for rings. Quotient rings R/I are built from them. And this is not just a construction - it is the mechanism by which mathematics literally manufactures new numbers from old ones.

**C = R[x]/(x²+1) is not a metaphor.** One equation is added: x² = -1. That kills all polynomials of degree above 1 (divide with remainder), and exactly what remains is a + bx with i = x. NTT (Number Theoretic Transform) is the same idea in Z[x]/(xⁿ+1). CRYSTALS-Kyber, the NIST post-quantum standard, uses this ring. A quotient ring as a cryptographic tool.

Key Ideas

• Ring: (R, +) is an abelian group + (R, x) is associative + distributivity links them
• Commutative ring: ab = ba. Ring with unity: there exists 1 such that ax1 = a
• Zero divisors: nonzero a, b with ab = 0. They break cancellation. In AES, an error here is a cryptographic break
• Ideal I: additive subgroup absorbing multiplication. Quotient rings R/I are built from ideals
• C = R[x]/(x²+1): complex numbers as a quotient ring. x² = -1 is a structural consequence, not magic
• GF(2⁸), Z/nZ, Z[x]/(xⁿ+1) - three rings on which modern cryptography rests

What's Next

Fields are special rings where every nonzero element has a multiplicative inverse. They give us the rationals, reals, complex numbers, and finite fields GF(pⁿ).

• Fields and Their Applications — A field is a commutative ring with unity, no zero divisors, where every nonzero element is invertible
• Polynomials — R[x] is the primary source of rings and fields through factorization

Вопросы для размышления

• Is Q[x]/(x²-2) a field? Why? (Hint: is x²-2 irreducible over Q?)
• NTT (Number Theoretic Transform) is FFT inside Z[x]/(xⁿ+1). What property of the ring allows replacing complex roots of unity with integer ones?
• Why is Z/nZ a field if and only if n is prime? How does this relate to the absence of zero divisors in Z/pZ for prime p?

Связанные уроки

• aa-03-homomorphisms — Homomorphisms are the language for understanding quotient rings
• aa-05-fields — A field is a ring without zero divisors plus inverses
• aa-09-polynomials — Polynomial rings are the primary source of examples
• aa-21-algebra-crypto — RSA, AES, post-quantum cryptography run on rings
• nt-01 — Z/nZ links number theory directly to ring structure
• crypto-04-algebraic-structures