An arithmetic circuit—the object a proof system ultimately asks a verifier to check—is a network of gates, each of which either adds or multiplies two previously computed values. A verifier must therefore calculate in a number system where both operations make sense at once and interact through the familiar laws of school algebra; and at certain moments—inverting a random challenge, cancelling a common factor from both sides of an identity—the verifier must divide as well. In what kind of structure can one do both, and when can one also divide? The structures of genuine cryptographic interest all support two interacting operations obeying the arithmetic laws of : the integers themselves, the rationals, the residue classes modulo , polynomials, matrices. The abstract capture of this pattern is the ring; the key special case in which division by every nonzero element is possible is the field. Fields are the natural arena for linear algebra and for the theory of polynomials, and the finite fields and are the computational substrate of essentially all the elliptic-curve and proof-system machinery later in the monograph.
The section also discharges a debt. Section 2 verified, concretely and one law at a time, that congruence classes admit an arithmetic, and promised that the verified laws would receive their structural names in due course. They receive them here: is re-read as a ring, indeed as the quotient of the ring by the ideal , and the theorem that is a field is stated in the language that the rest of the series uses. As a standing convention we assume from §3 only the theory of abelian groups; additive structure is written additively with identity , multiplicative structure multiplicatively with identity .
A ring is a set equipped with two binary operations and such that:
is an abelian group: addition is associative and commutative, there is an element with for all , and every has an additive inverse with ;
multiplication is associative: ;
there is a multiplicative identity with for all ;
multiplication distributes over addition on both sides: and .
The ring is commutative if moreover for all . We write for , let multiplication bind tighter than addition, and call the zero and the unity of the ring.
Conventions in the literature vary. Some authors omit requirement (3), saying “ring with unity” for the notion above and “rng” for the weaker one. In this monograph every ring has a , and the structure-preserving maps between rings—the ring homomorphisms of 4.21 below—are required to preserve it. Moreover “ring” frequently means “commutative ring” in the examples that matter to us; commutativity is always stated explicitly when a result depends on it.
The distributive law is the only axiom coupling the two operations, and a surprising amount of everyday algebra follows from it alone. The following identities are used constantly and, after this proposition, without comment.
Let be a ring and . Then:
;
;
;
for all integers , , where denotes the -fold additive multiple (, , and , as for any abelian group, §3).
(1) From and distributivity, ; adding to both sides leaves . The computation for is symmetric.
(2) By distributivity and (1), , so is the additive inverse of , that is, ; likewise gives .
(3) Applying (2) twice, , the last step because negation is an involution in the abelian group .
(4) First fix and show for by induction: the case is (1), and by distributivity and the inductive hypothesis. For write with ; then by (2). The same argument in the first factor gives for all , and combining,
the final equality being the usual bookkeeping for iterated multiples in an abelian group, which we omit. □
Nothing in 4.1 forces . If in a ring , then every satisfies by 4.3(1), so : the zero ring (or trivial ring), a legitimate ring in which both operations are the only possible ones. Whenever the zero ring must be excluded we impose the assumption explicitly; the definition of a field below builds in as a standing assumption.
The integers form the prototype commutative ring; much of ring theory consists of isolating which features of survive in generality.
The rationals , the reals , and the complexes are commutative rings—indeed fields, in the sense of §4.4.
The residue classes for —in this section’s examples we abbreviate the class of Definition 2.22 to when the modulus is clear—under the induced operations form a commutative ring whose additive group is the cyclic group of order (§3); this is 4.6 below. We write , or when no confusion threatens. The case gives the zero ring of 4.4.
The polynomial ring over a commutative ring consists of the polynomials with coefficients , added coefficient-wise and multiplied by expanding and collecting powers of ; it is a commutative ring with the same and as (the constant polynomials). The theory of polynomials over a field is developed in its own section later in the volume.
The matrix ring of matrices over a commutative ring , , is a ring under matrix addition and multiplication. It is not commutative for and , even when is commutative: in ,
This is the first important noncommutative example.
The product ring of two rings carries the componentwise operations, with zero and identity ; likewise any finite product .
The zero ring .
The third example is the one this monograph computes in, and it is the one whose ring structure was promised rather than named in §2. We now discharge that promise.
Let . The operations
are well defined and make a commutative ring with additive identity and multiplicative identity . It has exactly elements.
The right-hand sides are defined in terms of chosen representatives , so we must check that different choices give the same class. This is exactly the compatibility half of Proposition 2.21: if and , then and , so and . The operations are therefore well defined on classes.
Every ring axiom is now inherited from the corresponding law of by passing to classes. For instance, distributivity:
using only the definitions and the distributive law of the integers. Associativity and commutativity of both operations follow by the identical pattern. The class is an additive identity and a multiplicative one, since and ; and because .
Finally, by the division algorithm every integer is congruent modulo to exactly one of (the least nonnegative residues, Definition 2.22 and the discussion following it), so the classes are distinct and exhaust : the ring has exactly elements. □
Two features of the integers now deserve names of their own. First, enjoys cancellation: a product of nonzero integers is nonzero, so a nonzero common factor may be struck from both sides of an equation. Second, division within is nonetheless rare: only divide . The next two definitions abstract these phenomena—units capture the elements one can divide by, zero divisors the obstruction to cancelling.
An element of a ring is a unit (or is invertible) if there exists with . Such a is unique: if and , then . It is called the inverse of and written . The set of units of is denoted .
For any ring , the set of units is a group under the multiplication of , called the group of units (or multiplicative group) of .
The identity is a unit (it is its own inverse), so . For closure, let ; then
and symmetrically , so is a unit with . Multiplication in is associative because it is associative in . Finally each is itself a unit, its inverse being ; so every element of has an inverse in , and the group axioms are verified. □
The units of the integers are : if in then forces .
In , , and every nonzero element is a unit: , , . Commutative rings with in which every nonzero element is a unit are precisely the fields of §4.4; this is their defining feature. Both qualifiers are needed: the zero ring of 4.4 satisfies the unit condition vacuously, and noncommutative rings satisfying it—the division rings—exist but are not fields.
In the matrix ring, is the group of invertible matrices. Over a field it is the general linear group , the matrices of nonzero determinant; the determinant belongs to linear algebra, treated later in the volume.
A nonzero element of a ring is a left zero divisor if for some nonzero , and a right zero divisor if for some nonzero . In a commutative ring the two notions coincide and we say simply zero divisor. A nonzero element that is neither is called regular (or cancellable).
The terminology “cancellable” is justified by the following equivalence: zero divisors are exactly the obstruction to dividing out a common factor.
A nonzero element of a ring is not a left zero divisor if and only if it is left-cancellable: implies for all .
Suppose is not a left zero divisor and . Then , using 4.3(2) to expand ; since is nonzero and not a left zero divisor, the factor must be , so . Conversely, suppose is a left zero divisor, say with . Then while : cancellation fails. □
A unit is never a zero divisor: if and , then . The converse fails in general—in every nonzero element is a non-zero-divisor, yet only are units—but every nonzero non-zero-divisor is a unit in a finite commutative ring, by the injectivity-implies-surjectivity argument that proves 4.29 below.
In , , so and are zero divisors. In general a nonzero class is a zero divisor precisely when : in that case while (as ); and when the class is a unit (Example 4.9(3)), hence no zero divisor by 4.12. Thus in every nonzero element is either a unit or a zero divisor—a dichotomy revisited from a structural angle by 4.29.
In a product ring with both factors nonzero, : product rings always have zero divisors.
In , the diagonal matrices and multiply to the zero matrix; more generally every nonzero singular matrix—the standard name for a square matrix that is not invertible—is a zero divisor there.
An integral domain (or simply domain) is a commutative ring with and no zero divisors: implies or . Equivalently, by 4.11, a domain is a nonzero commutative ring in which every nonzero element is cancellable.
The residue rings sort themselves neatly against this definition, and the sorting is governed by primality.
Let . The ring has no zero divisors if and only if is prime; that is, is an integral domain if and only if is prime.
If is composite with , then with both factors nonzero (their representatives lie strictly between and ), so has zero divisors. Conversely let be prime and suppose , that is, . Euclid’s lemma for primes (Lemma 2.17) gives or , that is, or . Since we also have , so is an integral domain. □
For prime the ring is in fact far better than a domain: every nonzero class is invertible, so it is a field—a term defined in §4.4, where the statement is proved as 4.26.
The integers form an integral domain—the example the name commemorates. Every field is a domain (4.28 below). The ring is a domain exactly when is prime (4.15; the composite case is witnessed concretely by Example 4.13(1)). If is a domain, so is the polynomial ring : let and be nonzero of degrees and —the largest indices carrying nonzero coefficients and , the leading coefficients. In the coefficient of is ; every term with or has a vanishing factor, and , , force , , so the coefficient equals , nonzero because is a domain. Hence . Non-domains include , product rings with two nonzero factors, and the matrix rings for (Example 4.13).
We next carry quotient formation from groups to rings. For an abelian group and any subgroup, the cosets themselves form a group (Proposition 3.35); the ring-theoretic analogue asks for the subsets of a ring by which one can quotient while keeping both operations, and the answer is the notion of an ideal. The treatment here is deliberately brief: we need ideals chiefly to construct conceptually and to indicate where the finite fields come from; a fuller development belongs to commutative algebra.
Let be a commutative ring. An ideal of is a subset such that
is a subgroup of the additive group : , and whenever ; and
absorbs multiplication by arbitrary ring elements: whenever and .
In noncommutative rings one distinguishes left, right, and two-sided ideals according to the side on which absorption holds; commutative rings suffice for this volume, and there the three notions coincide.
Despite containing and being closed under the ring’s operations in the sense above, an ideal is almost never a subring: if an ideal contains —or, by the same absorption argument, any unit , since then —then for every , so . The only ideal containing a unit is the whole ring. This little observation will carry real weight: it is the reason a field has no ideals other than the two trivial ones, and hence no interesting quotients.
In any commutative ring , the subsets and are ideals—the trivial and improper ideals respectively.
For , the principal ideal generated by is
the set of multiples of ; absorption holds because . In , the principal ideal is the set of multiples of . In fact every ideal of is principal: an ideal contains a nonzero element and hence (closing under negation) a positive one, so it contains a least positive element by well-ordering; for any the division algorithm gives with , whence by absorption and subgroup closure, forcing by minimality; so . This sharpens the observation of Remark 2.12, where ideals of first appeared as the sets of Bézout combinations.
For , the ideal generated by is , the smallest ideal containing them all.
An integral domain in which every ideal is principal, as in (2), is called a principal ideal domain (PID).
Let be an ideal of a commutative ring . Since is a subgroup of the abelian group , the additive cosets form the quotient group under coset addition (Proposition 3.35). Define a multiplication of cosets by
With the operations of 4.19, the set is a commutative ring—the quotient ring of by —with zero and identity . In particular the coset multiplication is well defined.
Well-definedness is the point at which absorption is needed. Let and be other representatives of the same cosets, with . Then
and each of , , lies in by the absorption property; hence and . The product coset is therefore independent of the representatives chosen.
The ring axioms now pass to cosets exactly as in the proof of 4.6. For instance, distributivity reads
and associativity and commutativity of both operations follow by the same pattern from the corresponding laws in . The coset is the additive identity, the multiplicative identity, and . □
One more definition names the maps under which ring structure is preserved; we need it to say precisely in what sense the quotient construction generalises the passage from to .
A ring homomorphism between rings and is a map with
for all . Its kernel is .
The kernel of a ring homomorphism out of a commutative ring is always an ideal: it is a subgroup of because is in particular a homomorphism of additive groups, and it absorbs because gives .
Take and . The cosets are literally the residue classes of Definition 2.22, and the coset operations of 4.19 are exactly residue arithmetic: the quotient construction recovers the ring of Example 4.5(3), and is the conceptual origin of modular arithmetic. The same construction with a different ring produces the general finite fields: quotients of a polynomial ring by the principal ideal of an irreducible polynomial of degree —irreducibility, the polynomial analogue of primality, is defined in §5—furnish the finite fields with elements. We record the recipe here and take it up in §6; the curves of Halo 2 and Orchard work over prime fields, so the prime case carries the main line of development.
Structurally, then, is the quotient of the ring by the ideal , and the map
is a surjective ring homomorphism with kernel . This is the prototype of every quotient construction used in the volume’s algebra: one starts from a ring, singles out an ideal of elements to be “declared zero”, and computes with cosets. On notation: we abbreviate to (as in the examples above) or drop the decoration altogether, writing plain , whenever the modulus is clear from context; and are used interchangeably; and always means this ring, never the -adic integers (which do not appear in this series).
A field is a commutative ring with in which every nonzero element is a unit. Equivalently, a field is a set with two operations and such that is an abelian group with identity , the nonzero elements form an abelian group with identity , and multiplication distributes over addition. Unwinding the definition: in a field one may add, subtract, multiply, and divide by any nonzero element, with . The group is the multiplicative group of the field. (Two points of the equivalence are not direct transcriptions. Passing from the first formulation to the second, one must show is closed under multiplication; that is 4.28 below. Passing back, the ring axioms must be checked for products involving : distributivity forces by the computation of 4.3(1), whereupon every product with a zero factor vanishes and the associativity, commutativity, and identity laws extend from to all of ; and holds because the group contains its identity .)
A subset of a field is a subfield when it contains and and is itself a field under the operations of restricted to . When is a subfield of , the larger field is called an extension field (or simply an extension) of ; the two phrases name one relation viewed from its two ends. More generally, an injective ring homomorphism between fields exhibits as an extension of the copy of inside it, and we permit ourselves the usual abuse of identifying with that copy.
The finite world of §2 already contains the series’ most important fields, and the unit criterion proved there identifies them at once.
If is prime, then every nonzero class in is a unit, so is a field; it is denoted . More generally, is a field if and only if is prime.
Let be prime and , so that . The only positive divisors of are and , so , and Theorem 2.24 makes a unit. Since for , the ring is a field. Conversely, if is composite with , then but , so is not a unit (Theorem 2.24 again) and the ring is not a field; and gives the zero ring, which is not a field because a field has by definition. □
The rationals , the reals , and the complexes are fields. The integers are not: has no inverse in .
For prime, is a field (4.26; 4.29 below recovers the same fact abstractly). It is called the prime field of characteristic —4.30 names the invariant—and is fundamental to every later cryptographic construction in the series. Its finite extensions with elements exist for every prime power, arising from the quotient recipe of Example 4.22, and are developed in §6.
The subset is a field: the inverse of a nonzero is , which again has rational coordinates. More generally the number fields, obtained by adjoining to roots of polynomial equations with rational coefficients, are fields.
For any field , the rational functions form a field under the usual arithmetic of fractions—the field of fractions of the polynomial ring .
Every field is an integral domain.
Let be a field. Commutativity and hold by definition. Suppose with . Then is a unit, and multiplying by its inverse,
Hence has no zero divisors. □
The converse fails: is a domain but not a field (Example 4.16). Finiteness, however, closes the gap entirely, and does so by a counting device worth naming, for it recurs. Call it the injectivity-implies-surjectivity argument: to invert an element of a finite structure, show that multiplication by is injective, conclude that it is surjective because an injective map from a finite set to itself must be onto, and read off a preimage of . The same device proves the claim of 4.12 that in a finite commutative ring every nonzero non-zero-divisor is a unit.
Every finite integral domain is a field.
Let be a finite integral domain and nonzero. Consider the multiplication map
It is injective: if , then , and since is a domain and this forces , that is, (equivalently, is cancellable by 4.11). An injective map from a finite set to itself is surjective: the image has distinct elements and sits inside , so it is all of . In particular lies in the image, so for some ; commutativity gives as well, so and is a unit. Since is a domain, , and every nonzero element has just been shown invertible: is a field. □
Applied to —a finite domain by 4.15—the theorem recovers 4.26. The two proofs differ instructively. The pigeonhole argument merely asserts that each inverse exists; the extended Euclidean algorithm of §2 computes it, in division steps. Cryptography needs both: the abstract statement to reason with, and the algorithm to run.
Every ring receives a canonical map from the integers, and the behaviour of that map is a fundamental invariant: it measures how much of survives inside the ring.
Let be a ring, and for let denote the -fold additive multiple of (so with summands for , , and ). The characteristic is the least positive integer with , if such an exists, and otherwise.
An equivalent formulation is often more useful. The map
is a ring homomorphism: additivity is the bookkeeping of iterated multiples in the abelian group , multiplicativity is 4.3(4) with —namely —and . Its kernel is an ideal of , hence of the form for a unique by Example 4.18(2), and is exactly this nonnegative generator: precisely when is injective, so that a faithful copy of sits inside , and when the kernel is .
The rings , , , and all have characteristic : no positive multiple of vanishes. For the residue rings, : the multiple vanishes, and no smaller positive multiple does, since for . In particular .
The characteristic of an integral domain—in particular, of a field—is either or a prime number.
Let be an integral domain with ; we show is prime. First : otherwise , making the zero ring (4.4) and contradicting in a domain. Suppose with . By 4.3(4),
so or since is a domain. Either case exhibits a positive integer smaller than whose multiple of vanishes, contradicting the minimality of . Hence admits no such factorisation, and being greater than , it is prime. □
Let be a field. If , the homomorphism embeds a copy of in , and dividing—possible in a field—a copy of as well. If , the image of is a copy of . The smallest subfield so obtained is called the prime subfield of ; every field is thus an extension of or of some , and the dichotomy between characteristic zero and characteristic pervades the subject. The fields underlying the cryptography treated in this series all have prime characteristic . There the “freshman’s dream” identity actually holds, and gives rise to the Frobenius endomorphism; both are developed in the finite-fields section (6.13).
The question that opened the section is now answered in full. A verifier that must add and multiply computes in a ring; the laws verified one at a time for in §2 are precisely the ring axioms, and the construction that produced them is the quotient of by the ideal . A verifier that must also divide computes in a field, and 4.26 says exactly which moduli provide one: the primes. The payoff theorem, 4.29, closes the circle with a purely structural guarantee: in a finite world there is no daylight between the absence of zero divisors and the presence of division—any nonzero finite commutative ring in which nonzero elements never multiply to zero is automatically a field. The prime fields certified by these results are the ground on which the volume now builds: polynomials, linear algebra, roots of unity, and elliptic curves are all developed over them in the sections that follow.