Rings and Fields: A programmer's perspective

This article explains what a ring and a field are in abstract algebra. This builds off of our group theory article, so make sure you’ve read that first.

If you don’t know what a monoid and an abelian group are, you won’t be able to fully appreciate rings and fields.

Ring

A Ring is a set with two binary operators such that

• under the first binary operator, the set is a abelian group

• under the second binary operator, the set is a monoid

• the second binary operator distributes over the first

Remember, a monoid does not have an inverse, but a group does.

We do not require the monoid to be commutative. If it is, we refer to this ring as an abelian ring.

To illustrate the statement “the second binary operator distributes over the first”, let our binary operators be □ and ☆, where □ is the first binary operator and ☆ is the second binary operator. The following must be true for the field:

(a □ b) ☆ c = (a ☆ c) □ (b ☆ c)

c ☆ (a □ b) = (c ☆ a) □ (c ☆ b)

Note how the first binary operator □ appears in the parenthesis on the left hand, then we apply the second binary operator ☆. That is what we mean by saying “the second binary operator distributes over the first.” We do not require c □ (a ☆ b) to distribute.

The following is not necessarily true of a ring:

(a □ b) ☆ c = c ☆ (a □ b)

Exercise: by a ring’s definition, why is the above statement not always true? What assumption is it making about the ring?

Example rings

The trivial ring

A ring with only {0} under addition and multiplication is a trivial ring.

Exercise: use the definition of a ring to show that the trivial ring is in fact a ring

The set of all polynomials is a ring

This is a bit more subtle. First we need to show that polynomials are an abelian group under addition. This checks out. If you add two polynomials together, you get another polynomial (closed) and the operation is associative. The identity element is zero (zero is a valid polynomial, think of it as 0x^2, 0x, etc). The inverse of an element is the coefficients multiplied by -1. When you add two polynomials with inverted coefficients like that, you get the additive identity 0.

For multiplication, we now show that polynomials are a monoid. The identity element is 1 (a polynomial of degree zero, i.e. 1x^0). Any polynomial multiplied by 1 is the original polynomial. Inverses do not exist, because you cannot invert x^2 to get 1 x⁻² is not a valid polynomial. Multiplying polynomials is obviously closed and associative. It should be obvious that multiplication is associative over addition for polynomials.

Square matrices of real numbers under addition and multiplication is a ring

Exercise: demonstrate this to be the case. Think carefully about what the identity elements are and whether an inverse always exists.

Note that matrix multiplication is not commutative in general, but this is okay. We only need to show it is a ring, not an abelian ring.

Should a ring always have an inverse?

This depends on who you ask. Some authors use terminology that a “ring with inverse” is separate from a “ring.” Some will say “rng” to denote the absence of an inverse.

For our tutorials, we assume the ring has an inverse, but not every author does.

Field

A field is a set with two binary operators such that

• under the first binary operator, the set is an abelian group

• under the second binary operator, excluding the zero element, the set is an abelian group

What does “excluding the zero element” mean? Consider the example of regular arithmetic over real numbers. A group requires every element to have an inverse. Under multiplication, the identity element is 1. However, zero has no inverse because you can’t multiply zero by something and get 1. A field allows us, in an informal sense, to “exclude the problematic element” so that the set becomes a group under the second binary operator.

There is no trivial field

It isn’t possible to construct a trivial field using one element.

Exercise: Why is that the case? Hint: how many identity elements are needed? Hint: remember, the definition of a field is that the zero element is removed. An empty set cannot be a group.

Addition and multiplication modulo 2: the smallest possible field

If we do addition and multiplication modulo two, our set is {0,1}. this meets the definition of a field. That it is a group under addition is easy to show.

The interesting part is that it is a group under multiplication when the 0 element is removed. That’s because 1 is its own inverse (and the identity element) under multiplication.

This field has it’s own Wikipedia page GF(2) if you want to read more about this.

The set of all integers under addition and multiplication is not a field

This is because the multiplicative identity is one, and there is no integer you can multiply 5 by to get 1, as 1/5 is not an integer, but a rational number.

The set of all integers under addition and multiplication is actually a ring.

The set of all rational numbers is a field

This follows from the definition.

Rational numbers are an abelian group under addition, this should be obvious.

They are also an abelian group under multiplication, if you remove zero. Without zero, every element has an inverse that produces the identity element 1.

We also know from primary school that addition and multiplication are associative.

Importantly, adding and multiplying rational numbers produces a rational number, so these operators are closed.

The set of all real numbers is a field

The difference between real numbers and rational numbers is that all rational numbers can be written as the ratio of two integers, but there are infinitely many more numbers that cannot be constructed that way. However, they both are fields for the reasons listed above for rational numbers.

Field extensions

If both rational numbers and real numbers are fields, what is the relationship between them? Real numbers are a field extension of rational numbers, and rational numbers are a subfield of real numbers.

First let’s define a subfield.

A set can have a subset. Because a field is a set, we can also have subfields.

For example, real numbers are a subfield of complex numbers, and rational numbers are a subfield of real numbers. Therefore, we can say that complex numbers are a field extension of real numbers, and real numbers are a field extension of rational numbers.

You cannot pick an arbitrary subset. The key is that the subfield needs to be closed under the two binary operators. For example, the field operators on rational numbers cannot produce a non-rational number (like π or √2), and field operators on real numbers cannot produce complex numbers, this makes the operator closed.

If we pick a random set of real numbers from the field of real numbers, this would be a subset, but not a subfield, because in general that subset won’t be closed over the binary operators.

Integers modulo a prime number is a field under addition and multiplication

Interestingly, although integers under addition and multiplication are not a field, integers modulo a prime number are. That’s because in modular arithmetic, every element in a finite field has a multiplicative inverse which can be calculated in python as follows:

p = 11 # must be prime
a = 6 # pick any element from [1,p], note that zero is excluded
a_inv = pow(a, -1, p)
assert (a * a_inv) % p == 1

You can read more here about multiplicative modular inverses.

Finite fields

Finite fields are used a lot in cryptography. One major advantage of finite fields is that we can do arithmetic on rational numbers of arbitrary precision. For example, it would normally take a lot of bits to represent

However in finite fields, this is just the numerator multiplied by the denominator’s inverse.

This does not mean we can recover the original rational number given an element in a finite field. The mapping from rational numbers to a finite field is (obviously) surjective, so the preimage is not unique.

But this doesn’t actually turn out to be a problem from a cryptography perspective. If we are trying to convince a verifier that we did some math on rational numbers correctly, the verifier only needs to check that the claim is true in the finite field.

The most common finite field you will encounter is integers modulo a prime number, sometimes written as ℤp, where p is a prime number.

A finite field (over a prime number) is sometimes called a Galois field.

Finite fields behave like regular fields.

Even though this seems trivial, it’s actually quite important. It means that any addition, subtraction, multiplication, and division we do with integers is also true in a prime finite field.

One important application is polynomials over finite fields. It may be very hard to imagine what this mathematical entity looks like, but that should not matter to you. Polynomials are just a combination of adding and multiplication, both of which are field operators. Therefore, their behavior doesn’t change when you do it over a prime finite field.

Sometimes students get thrown off that “it just works?!” when you do math modulo a prime number. As long as you are only doing the field operators, then the field structure is preserved. Even Vitalik Buterin referred to this “it just works” property as “spooky kind of arithmetic which is self-consistent”. But it doesn’t need to be spooky. As long as you accept that addition and multiplication modulo a prime is a field, then you can always fallback on the principle that “if it works in regular arithmetic, it works in modular arithmetic.”

If you do operations like, let’s say, taking the square root or taking the derivative, then you lose the guarantees – those are not the binary operators for a field.

Thankfully, addition, multiplication (and their inverse operations) are generally all we need to accomplish zero knowledge proofs.

Learn more with RareSkills

This article is part of the study materials for our Zero Knowledge Course.