Finite Field Fun: A lightweight introduction to finite fields and their applications for engineers, computer scientists, and others

By Riccardo Bernardini

Finite field theory is a powerful algebraic tool used in many modern applications: from cryptography to digital transmission. The traditional way to introduce finite field theory is within a course of algebra, after the introduction of groups and rings. This makes finite field theory a challenging subject for those who need to use them, but do not have a strong algebraic background (e.g., electrical engineers, software engineers, programmers,..). This book aims to give a rigorous and solid introduction to the matter, while requiring only the basic notions about complex numbers. At the end of the book, the readers should be able to use finite fields in their application and should also find easier to read more advanced books on this matter. Part of the book is also devoted to describe the algorithms to actually use finite field in software, a crucial aspect not always discussed in algebra books (aimed to a more mathematical audience).

• Language: English
• Publisher: Youcanprint
• Release date: Jun 28, 2023
• ISBN: 9791221469950

Book preview

𝔽inite 𝔽ield 𝔽un

A lightweight introduction to finite fields and their applications for engineers, computer scientists, and others

Riccardo Bernardini

To my wife

Contents

I  Preliminaries

1 README.1st (aka, Introduction)

1.1 What, Why, for Whom?

2 Preliminary notions

2.1 Groups

2.1.1 Cyclic groups

2.2 Rings

2.2.1 Ring characteristic

2.2.2 Zero divisors and integrity domains

2.2.3 Group of units

2.2.4 Fields

2.3 Vector spaces and Algebras

2.3.1 Vector spaces

2.3.2 Algebra

2.4 Homomorphism

2.5 Notation: computational complexity

II  The Theory

3 The clay: modular arithmetic

3.1 Integer division remainder

3.2 Sum and product modulo N

3.2.1 The domain: the set of classes modulo N

3.2.2 Addition modulo N

3.2.3 Product modulo N

3.A ℤ2ν and ν-bit arithmetic

3.B The case N = 2ν−1

4 The brick: Fields with prime size

4.1 Division in ℤN

4.2 Logarithms for finite fields

4.2.1 Computational issues

5 The full building: 𝔽pℓ

5.1 Squaring, that is, getting 𝔽p² from 𝔽p

5.2 General construction for 𝔽pℓ

5.A Field extensions: not only for finite fields (with a bit of chaos)

III  The practice

6 Down to the bits: doing math in 𝔽q

6.1 Linear representation

6.1.1 Generic basis

6.1.2 Monomial basis

6.1.3 Normal basis

6.2 Matrix representation

6.2.1 Not only for finite fields…

6.3 Exponential representation

7 Some applications

7.1 Secret sharing

7.1.1 Geometry to the rescue!

7.1.2 Making it practical

7.2 Peer-to-peer streaming with residential users

7.3 Error correction codes

7.3.1 Error correction codes in a nutshell

7.3.2 Linear codes

7.4 Physically Unclonable Functions stabilizers

7.4.1 What is a Physical Unclonable Function?

7.4.2 Stabilizers: why and how?

7.5 Diffie-Hellman key exchange

7.6 Elliptic curves

7.6.1 Elliptic curves on ℝ

7.6.2 The finite field case

A Example of secret sharing with Octave/Matlab

B Algorithms

B.1 Euclidean algorithm for GCD

B.2 Numerical linear algebra in 𝔽q: LUP factorization

B.2.1 Elementary operations

B.2.2 Overview of the LUP factorization procedure

B.2.3 Bringing A in upper triangular form

B.2.4 Linear system solution by back-substitution

B.3 Exponentiation by squaring

B.3.1 Computational cost and side channel attacks

B.3.2 With signed digit representation

C Details on Elliptic Curves

C.1 Why Δ≠0?

C.2 Derivation of the analytical expressions

D Answers to Exercises

Index

Part I

Preliminaries

Chapter 1

README.1st (aka, Introduction)

1.1

What, Why, for Whom?

What is a finite field? Why should I care?

A field in algebra is, roughly speaking, a set endowed with the well-known four operations: sum, difference, product and division. The three most common examples of fields, with whom you are surely acquainted, are the rational numbers ℚ, the real numbers ℝ and the complex numbers ℂ. A finite field is… well, a field with a finite number of elements.

OK… and why should I care?

Fields are very powerful structures; for example, by using a finite field one can construct finite vector spaces. Although this could sound as fun for mathematicians only, the possibility of introducing the firepower of geometry in a finite context can provide simple solutions to problems that would look bewildering at first, for example: sharing secret safely among collaborators (Section 7.1), distributing video content with insufficient upload bandwidth (Section 7.2), correcting transmission errors (Section 7.3), creating tokens impossible to clone (Section 7.4), exchanging cryptographic keys (Section 7.5), creating special curves made of a finite set of points (used in cryptography, Section 7.6). From a more theoretical point of view, finite fields can be used to decide if a polynomial equation is solvable by radicals (e.g., like a second degree equation) or if a figure can be drawn using a compass and a ruler [1].

Some of these problems can sound hopeless at first, but with the tools described in these notes the solution is kind of Oh, yes, of course, that is easy…

OK, I am sold, this is interesting, but why this book?

There are out there many books on finite fields and their applications [1, 2, 3, 4, 5]. Most of them, however, are addressed to mathematicians and a background in abstract algebra is required if you want to profit from them.

However, there are some professional figures (e.g., engineers, computer scientists, programmers) that may need this tool for their applications. Your mileage may vary (a lot), but in my experience finite fields are not taught in depth in engineering/CS courses; if necessary, they are briefly introduced in those courses that need them (e.g., digital communication or cryptography). Said ad hoc introduction is necessarily brief and may leave the student unsatisfied and with many doubts.

This book wants to cover the intermediate ground: my aim is to give a nice introduction to finite fields with the idea that the students at the end will be able to read technical papers and books aimed to a more mathematically oriented audience and use finite field arithmetic with the same ease they use complex numbers; but without the need of a strong algebraic background.

Of course, this has consequences, since the algebraic theory found in math books is not there just for fun, rather it is necessary for a rigorous and correct treatment. This means that there are some portions that I will not be able to cover, especially some proofs that with the right background would be quite easy, but in this book I must resort to It can be proved that…see […] for details. However, most of the theory can be introduced with just a basic knowledge of math and set theory.

At the end the students should be able to work autonomously with finite fields, using them to develop solutions for new problems.

Is this book like a YouTube tutorial?

I would dare say it is not; although it is on an easier level than an abstract algebra book, it is also more complete than just a tutorial. The typical objective of a tutorial is to give you an introduction and a general feeling of the matter, but usually after a tutorial you are not able to apply the concepts described in the tutorial to practical problems. My objective instead is to enable you to use finite fields autonomously in practical problems.

So, this book would not allow me to skip my Algebra course?

It depends on who you are and on your goals. If you are an engineering/CS student who needs to work with finite fields, this book can be sufficient for you. If you are a mathematician who is taking an Algebra course, I am afraid that this book could not cover all the ground your Algebra course does. However, if you are confused by all the technicalities in your course and you are longing for some intuition, this book could bootstrap you.

Did someone say source code?

Yes, indeed. On GitHub at URL

PIC

  https://github.com/riccardo-bernardini/fff/

you can find some software implementation of most of the algorithms described here. I did this for two reasons: (i) to show you some real-life code that you can study to understand better the matter of this book and (ii) to give you some software ready-to-be-used as a nice complement to this book.

I really enjoyed this book, but now I want more

There is plenty of books on this matter, both focused on finite fields or about more general algebra. The two main books I used while writing these notes are the Basic Algebra I by N. Jacobson [1] and Finite Fields by R. Lidl and H. Niederreiter [2]. Another classical algebra book is Topics in Algebra by I.N. Herstein [4]. Finally, material on finite fields can be found also on some number theory book like A Classical Introduction to Modern Number Theory by K. Ireland et al. [5].

Finally, a word about this format…

Electronic books are nice because of their convenience, however the current format (epub) is more suited to novels than to technical books since it does not play nicely with figures, tables and equations. Moreover, what you see depends largely on your viewer, its physical size, the fonts has installed and so on. This to say that it is easier to control the appearance of a text on a physical book rather than on an e-book. I would advise to read this book with a light background, not a dark one. The reason is that some complex equations, that cannot be represented in epub, have been converted into images and included as such. The problem is that the background and the ink of said images is fixed and would not change if you change the background.

I tried reading this book with few different viewers and, in general, the results are good. You could experience some stylistic inconsistencies, but nothing that prevents understanding the content.

Chapter 2

Preliminary notions

As said in Chapter 1, the preliminary notions required to the reader are quite basic: integers, polynomials, set theory and complex numbers. However, some basic algebraic language will help a lot in the description. The goal of this chapter is to give a fast recall of the main concepts. If you are already acquainted with groups, rings, fields, algebra and homomorphisms you can move on directly to next chapter or, maybe, just skim this chapter in order to be in sync with the notation.

2.1

Groups

Groups are one of the simplest algebraic structure and as such they can model many mathematical objects. A group is just a set G together with an operation (here denoted with ⋅) that combines two elements a,b ∈G together to give a new element a⋅b ∈G. We require that the operation must be well behaved enough, more precisely

It is associative

that is, for every a,b,c ∈G it holds

This allows us to write expressions like a⋅b⋅c without ambiguity. It has a neutral element

That is, there is e ∈G such that for every a ∈G

It has an inverse

that is, given any element a ∈G one can find its inverse, denoted as a−¹ such that

Note that we do not require commutativity, that is, it can happen that for some a,b ∈G, a⋅b≠b⋅a (think, for example, to the matrix product). If the operation is commutative, the group is said to be Abelian or commutative.

Notation 2.1

In the definition above we used the multiplicative notation with the operation denoted with ⋅, the neutral element with e and the inverse with a−¹. This is common when talking about a generic group. If the group is commutative, it is common to use an additive notation with the operation denoted with +, the neutral element with 0 and the inverse with −a.

It is common to collect set and operation in a single notation like (G,⋅) or (G,⋅,e).

Remark 2.1

It is possible to weaken the notion of group, by removing some axioms. For example, if we do not ask that every element has an inverse, we get a monoid (e.g., the integers with the product); if we do not even require a neutral element we get a semi-group.

— ∙—

Exercise 2.1

Simple and (maybe) fun exercise: prove that (i) the neutral element is unique and (ii) the inverse is unique.

See D.1 at page 457

Example 2.1

Many mathematical objects can be modeled as groups, for example

(ℤ,+), that is, the integers ℤ with the sum, but also the reals ℝ, the rationals ℚ, complex numbers ℂ, quaternions, … and some strange stuff like the surreal numbers (Yes, they exist [6])

(ℝ∗,⋅), that is, the set of non-zero reals ℝ∗= {x ∈ ℝ : x≠0}(or rationals ℚ∗, or complex numbers ℂ∗) with the product

The polynomials with the sum

Non-null rational function (ratio of polynomials) with the product

Vector spaces with the sum between vectors

Rotations in ℝNwith rotation composition

({0,1},XOR), that is, the set of bits {0,1}with the exclusive or as composition (check it)

(𝒫(X),△), that is, the power set of X (that is, the set of the subsets of X) with the symmetric difference △ defined as

where A,B ⊆X. In other words, A△B contains the elements that belong to A or to B, but not both. What is the neutral element? What is the inverse of A?

Example 2.2

If the examples in Example 2.1 are too vanilla for your taste, check out the Elliptic Curve group described in Section 7.6

2.1.1

Cyclic groups

If (G,⋅) is a group, g ∈G and n ∈ℤ, it is natural to define

Clearly definition (2.5) applies when the multiplicative notation is used; if instead the additive notation is used one defines ng in a similar way, using repeated sums.

A very special (and important) type of group is represented by the cyclic groups that can be generated by taking successive powers (or sums) of a single element.

Definition 2.1. A group (G,+) is said to be cyclic if there is γ ∈G