Ring and Field Theory | Part 3 | Understanding Cryptography Through Mathematical Primitives

Paul Vienhage - Smart Contract Auditor and Engineer
November 26th, 2018
Proof and Set Theory Understanding Crpytog Image

In the last post in the Authio Math Series we talked about groups. Groups are an abstraction of the numbers that we are familiar with but they lose most of the properties of numbers. Rings and fields are also abstractions of the numbers but they enforce much more of the properties we are familiar with. In this post we will define rings and fields and we will examine how fields are used in encryption. Then to show how powerful these definitions are we build a new type of number: the p-adic number. Finally we tie in with the previous post and prove the founding theorem of Galois Theory.

What is a ring?

A ring R is a set with two functions called binary operations: + : R × R → R and ⋅ : R × R → R that have the following properties:

  • (a +b) + c = a + (b + c)
  • a+b = b+a
  • There exists a 0 such that for any a, a+0 = a
  • For all a ∈ R, there exists -a ∈ R such that a + (-a) = 0
  • (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)
  • There exists an 1 ∈ R such that for all a ∈ R : 1 ⋅ a = 1 = a ⋅ 1
  • a ⋅ (b +c) = a ⋅ b + a ⋅ c
  • (b + c) ⋅ a = b ⋅ a + c ⋅ a

For a taste of what these properties imply lets consider the case where R is a ring and 1 =0. Let a ∈ R which has that a ≠ 0 then given that x ⋅ 0 = 0 as 0⋅ x = (0 + 0)⋅ x = 0⋅ x + 0⋅ x which implies 0x = 0. So then a⋅ 1 = a = a ⋅ 0 = 0 thus this ring only contains the element 0. This answers a classic question in math, why isn’t one equal to zero? because if it was math wouldn’t be that interesting.

Example 1: Modular Rings
Consider the set ℤ/nℤ = {x ∈ ℕ ∪ {0} | x < n } then we define two operations on this set a + b = a + b mod n and a ⋅ b = a ⋅ b mod n. We can get associativity and commutivity of this addition from these properties for addition of natural numbers. The additive inverse of a is n-a and the additive identity is 0. Similarly, the multiplicative identity is 1. Left distribution and right distribution can be shown from the properties of mod.

Example 2: Polynomial Rings
We can define another type of ring denoted ℝ[X] to be the ring formed by all real polynomials. Ie. ℝ[X] = { f(X) | f is a finite polynomial with real number coefficents }. Then given two polynomials f(X) = c₀ + c₁ X + … + cₙ Xⁿ and g(X) = d₀ + d₁ X + …+ dₘ Xᵐ. Note that we implicitly define cₖ = 0 for k > n and dₖ = 0 for k > m. Then g + f = (c₀ + d₀) + (c₁ + d₁) X + …+ (c_(max(n,m)) + d_(max(n,m))) X^{max(n,m)} . We define the ring multiplication as the traditional multiplication of polynomials. The additive identity is the polynomial 0(x) = 0 and the multiplicative identity is 1(x) = 1. The other properties follow from the properties of real number addition and polynomial multiplication.

Ring 2.0, the Field

In a general ring we are missing something that most people would take for granted in a number system. Namely there are elements a , b ∈ R in some rings which have that a ≠ 0, b ≠ 0, but a ⋅ b = 0. In the real numbers we are familiar with however nothing can divide zero besides zero. A ring with no nonzero zero divisors is called a domain.

Another property we might want is that any number has a multiplicative inverse. If we have that a ∈ R (a≠ 0) there exists an element a⁻¹ ∈ R such that a ⋅ a⁻¹ = 1 then the ring is called a field. This could also be stated as that (R, ⋅) is a group. Requiring that a ring have multiplicative inverses is a fairly strong condition as it implies that the ring is also a domain. Proof: a⋅ b = 0 if both a ≠ 0 and b ≠ 0 then since R is a field there exists a⁻¹ and a⁻¹ ⋅ a ⋅ b = a⁻¹ ⋅ 0 = 0 so then 1 ⋅ b = b = 0. Thus there cannot be any nonzero zero divisors and any field is a domain.

Example 3: The Rational Field
The simplest example of a field is the field that in many ways inspired what a field is supposed to be. Consider the set ℚ which is all fractions. If we use elementary school addition and subtraction as our binary operations we can get a field. Proof: 0 is our additive identity 1 is our multiplicative identity. The other ring properties follow from the rules of addition and multiplication we learned in elementary school. Finally q = a/b ∈ ℚ has a multiplicative inverse q⁻¹ = b/a ∈ ℚ as a/b ⋅ b/a = 1. Thus ℚ is a field.

Finite Fields: The core of old school cryptography

In the core of the the most popular encryption systems is a finite field. For example to use Diffie-Hellman we should pick a large prime then we use the properties of modular mathematics and the difficulty of the factoring problem to build our encryption algorithm. When we break this down we might hit a crucial question: why are primes important to this algorithm? Before we knew about fields the might have been able to do is wave our hands around vaguely and say that primes are special because they are. But now we can say something concrete: ℤ/ nℤ is a field if and only if n is prime. If we pick a non prime modular size then zero divisors have weaker encryption properties because some elements will have lesser order, so we should always use finite fields.

Proof: ℤ / pℤ is a field, first we note that any element has order p-1. We note that ℤ / pℤ is a cyclic group of prime order thus each element has order p-1. By pigeonhole principle (if you put n pigeons in n holes either there’s a pigeon in each hole or a hole with two pigeons), since their are p-1 other field elements and each of x, 2⋅ x, 3 ⋅ x, … , (p-1) ⋅ x is different (as the order of x is p-1) there must be some c ⋅ x = 1. c is the required inverse so ℤ /pℤ is a field. Next consider ℤ/ nℤ where n = km then k ∈ ℤ / nℤ and m ∈ ℤ / nℤ. Then m⋅ k = 0 so ℤ / nℤ isn’t a domain and thus it cannot be a field.

p-adic Fields

The 2-adic integers with corresponding Pontryagin dual group

Often there is debate about if mathematics is discovered or invented, sometimes mathematics is created to describe the world but others the mathematics is created first and then later applied to the real world. The p-adic numbers are an example of a concept that has been invented by mathematicians before real world applications have been found. We cover them here not because “p-adic blockchain” is going to be the next trendy startup, but because the process of invention of purely abstract mathematics is exactly the type of thinking that can drive disruption in tech.

Invention in mathematics is a concept that would seem alien to most high school or even college math students. Math is taught as the capital T Truth and seemingly immutable, but every day new math is invented and old mathematics extended and updated. Math is invented by asking the same question that tech disruptors ask: what is everyone assuming and are they right? If you find an implicit assumption and can break it you have created new mathematics. p-adic numbers break the assumption that the only way to put decimals in order between the fractions is the way we learned in school.

How would someone have thought to put the decimals in another order? Well order depends on the measurement of distance between two numbers. Can we break the definition of measurement of distance? What if we decided to write each rational a/b as p₁ ᵏ₁ * p₂ ᵏ₂ … pₙ ᵏₙ where the k s are integers, then defined |a/b|ₚ= the power of p in the decomposition of a/b. This may be weird at first. But this definition actually has all of the properties mathematicians came up with when they defined all of the things they would want from a function that measures things in general. It will actually be consistent to measure the distance between two fractions as |a/b - c/d|ₚ, however that consistency does not prevent a real disruption to the way we think about ordering things.

The p-adics non-archimedean meaning we can have numbers for which |a + b|ₚ > max{a , b}, a totally mind bending result when you come from normal real numbers. This will make more sense when we fully define what the p-adic numbers even are.

Construction: We will define the p-adic integers as a set in one to one correspondence with the normal integers. Namely each p-adic integers is a series (aₙ) where each aₙ ∈ ℤ / pⁿℤ and if n<m then aₙ ≡ aₘ mod pⁿ . Every integer can be written in such a form and will eventually terminate in an infinite sequence of the integer itself. 7 corresponds to (1, 3, 7, 7, 7, 7, 7, …) in the 2-adic rational system. We can define the normal modular addition and multiplication on each corresponding element of two serieses and thus the p-adic integers inherit the field structure from ℤ / pⁿℤ. Which means that the p-adics integers don’t have zero-divisors and since there are no zero divisors we can form the field of fractions of p-adic integers. That field of fractions makes each p-adic number the infinite sum of a*pᵏ where k ∈ ℤ and p ∤ a.

This construction actually gives a coherent version of the decimal numbers, which has most of the properties we want from numbers. Without going into detail, they provide a set of numbers with interesting intrinsic geometry and properties that make some calculation easier. The lesson is that to invent new things we need to question our assumptions and rebuild our tools to work in a world without our assumptions.

Galois Theory

In the previous article we talked about how fifth degree polynomial could not be solved using a formula in terms of fifth or lower roots of rationals. Now that we have defined fields we have the tools to actually prove that.

Definition: Given a pair of fields (F, +₁, *₁) and (L, +₂, *₂), such that F ⊆ L. We call L a field extension of F if given x, y ∈ F we have that x +₁ y = x +₂ y and x *₁ y = x *₂ y. Which is a symbolic way of says the field operations in L when restricted to F are the same as the field operations in F.

Example: Take ℚ as the field F, then define a field {a + b√2 | a, b ∈ ℚ} which has the following operations for x∈ {a + b√2 | a, b ∈ ℚ} and y∈ {a + b√2 | a, b ∈ ℚ} then x +y = (x₁ + y₁) + (x₂ + y₂)√2 and x*y = (x₁ * y₁ + 2 * x₂ * y₂) + (x₁ y₂ + x₂ * y₁) √2 . Proving this is a field is slightly pedantic so we will not present it here. However it is clear this is a field extension of ℚ as elements of ℚ in {a + b√2 | a, b ∈ ℚ} just have b=0 so for rationals x and y we have x +y = (x₁ + y₁) + (x₂ + y₂)√2 = (x₁ + y₁) + 0*√2 = x₁ + y₁ and x*y = (x₁ * y₁ + 2 * 0* 0) + (x₁ *0 + 0* y₁) √2 = x₁ * y₁ . Thus the operation we defined collapses to the normal addition and multiplication of rationals.

We generalize the previous example to extension of the rationals by any root using the notation ℚ[x₁, x₂, … , xₙ] = {y₀ + y₁ x₁ + y₂ x₂ + … + yₙ xₙ | y₁, y₂, … , yₙ ∈ ℚ}. Using this notation we can define the Galois group of a field extension.

Definition: An automorphism of a field extension L over F is a function f which is an automorphism of the field L [note that an automorphism is a isomorphism from the field L to itself] which additionally has that for all x∈ F that f(x) = x. What this definition means intuitively is that the automorphism of a field extension is a function which moves the elements of the extension around consistently without touching the base field.

Definition: The Galois group (G, ∘) of a field extension L over F is defined with G = {f | f is an automorphism of the field extension L over F} and ∘ is the function composition. Note that in general sets of functions under functional composition are a group if they are closed. We conclude that (G, ∘) is a group since f∘g (x) = g(f(x)) = g(x) = x if x ∈ F and f and g are field extension automorphisms, thus f∘g is a field extension automorphism and G is closed under ∘.

Given a group H and a group G, H is said to be normal to G denoted H⊲G, if H divides G nicely. We won’t go into what exactly that means, just note that if H⊲G then G/H (G divided by H) is a group. A group G is called solvable if there exists a sequence {Gᵢ} such that {e} ⊲ G₁ ⊲ G₂ ⊲ … ⊲ Gₙ with Gₙ = G and such that G_{i+1} /Gᵢ is a cyclic group.

Theorem: A polynomial f is solvable by radicals only if the Galois group of ℚ[r₁ , r₂, …, rₙ] is solvable.

Proof: Assume that the polynomial f is solvable by radicals then each root rᵢ can be expressed as the linear combination of solutions of equations xⁿ + a = 0 and each of these is up to a constant factor a root of unity. Roots of unity naturally form cyclic groups of order n. Unfortunately since we have have not exactly defined the property “normality” we cannot exactly prove the Galois extension is normal. Rather we need to settle for the fact that our field extension will be composed of extensions by roots of unity and our Galois group is thus approximately the “product” of the cyclic groups they naturally form. Which our divisible series will divide off a layer of cyclic root of unity groups at each step.

Given that a polynomial is solvable by radicals only if its root’s field extension’s Galois group is solvable we can prove that no general polynomial of degree greater than or equal to 5 is solvable by radicals.

Proof: In general we can construct a polynomial of degree n whose roots form a field extension of ℚ which has a Galois group that is the symmetric group on n elements. Sₙ for n ≥ 5 is simple, meaning that it has no divisors. You may recall that in the previous article that symmetric groups were one of the finite simple families of groups. Since Sₙ has no divisors it cannot have a string of divisors leading to zero and thus is it not simple, ergo f is not solvable by radicals.

A more detailed treatment of these proofs can be found in http://www-users.math.umn.edu/~garrett/m/algebra/notes/23.pdf I recommend it to people who are curious about a more formal mathematical proof.

Thats it! You made it to the end of the most formal and complicated mathematical article in this series so far. Next time we will be turning back to the applications of what we have learned to real computer science, and covering elliptic curves, cryptography, and digital signature algorithms.