Finite Field Fun E-Book

Riccardo Bernardini

• Herausgeber: Youcanprint
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch
• Veröffentlichungsjahr: 2023

Beschreibung

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).

Leseprobe

𝔽inite 𝔽ield 𝔽un A lightweight introduction to finite fields and their applications for engineers, computer scientists, and others

Riccardo Bernardini

To my wife

Contents

Part IPreliminaries

Chapter 1README.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

 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 2Preliminary 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

(2.1)

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

(2.2)

It has an inverse

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

(2.3)

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.1In the definition above we used the “multiplicative” notation with the operation denoted with ⋅, the neutral element with e and the inverse with a−1. 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.1It 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.1Simple and (maybe) fun exercise: prove that (i) the neutral element is unique and (ii) the inverse is unique.

See D.1at page 457

Example 2.1Many 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 productThe polynomials with the sumNon-null rational function (ratio of polynomials) with the productVector spaces with the sum between vectorsRotations 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

(2.4)

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.2If the examples in Example 2.1are 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

(2.5)

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 such that every group element g ∈G can be written as multiple of γ, that is,

(2.6)

An obvious example of cyclic group is (ℤ,+), since every integer n can be obtained by repeatedly adding 1 to itself; a less obvious example is ({0,1},XOR) (check). Other examples of cyclic groups will be encountered in Chapters 3and4.

2.2 Rings

While groups are sets with a single composition law (e.g., the integers ℤ with the sum), a ring is a set with two composition laws that, roughly speaking, act like sum and product. More precisely, a ring is a set ℛtogether with two composition laws (usually denoted with operators ⋅and + or similar) that satisfy the following properties

See Table 2.1for few examples of rings.

Notation 2.2The notation usually used for rings is (ℛ,+,⋅) that collects the set and the two operations in a single triple. This notation can be simplified to ℛif the operations are clear from the context and enriched to (ℛ,+,⋅,0,1) if we want to write explicitly the neutral elements.

Warning 2.1Some authors (e.g., [2]) use a definition of ring slightly different from ours, not requesting the existence of a multiplicative identity; if a multiplicative identity exists, they call it ring with identity. Other authors (e.g., [1]) follows our convention and call a ring without identity a rng.

Although these axioms remind the behavior of usual “numeric” product and sum (e.g., for integers), they are much more general and care must be exercised.

Table 2.1: Examples of rings. ℛN×N is the ring of square matrices with elements in ring ℛ, ℝ[x] is the ring of real coefficient polynomials, ℝ[x,x−1] is the ring of Laurent polynomials with real coefficient (they can have both positive and negative powers of x), ℝ(x) is the ring of rational functions with real coefficients.

Integrity Group of Example Commutative Domain Units ℤ {−1,1} ℚ, ℝ, ℂ x≠0      ℛN×NdetM ∈ℛ∗     ℝ[x] Constants ≠0 ℝ[x,x−1] Monomials ≠0 ℝ(x) x≠0

2.2.1 Ring characteristic

As we did for groups, we can define the product of an integer n with a ring element a ∈ℛusing repeated sums

(2.9)

Definition 2.2 (Ring characteristic).Given a ring (ℛ,+,⋅,0ℛ,1ℛ), the smallest positive n such that

is called characteristic of ℛ and denoted as char(ℛ). If no such n exists (that is, n 1ℛ≠0ℛfor every n > 0), char(ℛ) is defined as 0.

In a ring ℛwith char(ℛ)≠0 it is possible to prove the following Rookie’s Lemma, useful in many occasions.

Lemma 2.1 (Rookie’s Lemma).Let ℛbe a ring of characteristic m. For every a,b ∈ℛthe following equality holds

(2.10)

Proof.An easy exercise. Hint: use the binomial expansion and checks that all missing terms have coefficients that are multiple of m. □

2.2.2 Zero divisors and integrity domains

It is an easy exercise (see Exercise 2.3) to prove that in every ring ℛ

(2.11)

that is, if one factor in a product is zero the result is always zero. Yes, I know, no big surprise here; however, the reverse implication does not need to be true, that is, in general one cannot deduce from

(2.12)

Definition 2.3 (Zero divisors).If a,b≠0 are such that a⋅b0, a is said to be a left zero divisor and b a right zero divisor. If an element is both a left and right zero divisor (e.g., if the ring is commutative), it is said to be simply a zero divisor.

Many rings have no zero divisors, for example: integers, polynomials, real numbers, … They, too, are important enough to deserve a special name.

Definition 2.4 (Integrity domain).If ℛhas no zero divisors (that is, if a,b≠0 implies a⋅b≠0), the ring is said to be an integrity domain.

Warning 2.2If we know that a,b,c ∈ℛ, a≠0, from

(2.13)

you would be tempted to deduce

(2.14)

by “dividing by a” both sides. However, if a is a zero divisor, this reasoning is invalid and (2.13) does not implies (2.14); for example,

(2.15)

It is however true that (2.13) implies (2.14) (even if a has no multiplicative inverse) when ℛis an integrity domain, seeExercise 2.2.

Exercise 2.2Prove the following cancellation law: if ℛis an integrity domain then

(2.16)

implies

(2.17)

even if a has no multiplicative inverse.

See D.2at page 459

2.2.3 Group of units

If a ∈ℛhas a multiplicative inverse, a is said to be a unit of ℛ.The set of the units of ℛwill be denoted as ℛ∗. It is easy to show (see Exercise 2.3) that ℛ∗is a group with the product inherited from ℛ; ℛ∗is called the multiplicative group or group of units of ℛ.

Exercise 2.3Prove that for every ring ℛ

Multiplying by zero always gives zero, that is, (2.11)

Multiplying a ∈ℛby −1 (the opposite of the multiplicative neutral element) gives the opposite of a, that is,

(2.18)Prove that the set of units ℛ∗is a group with respect to the product of ℛ.See D.3at page 460

Exercise 2.4Prove that

The set of bits {0,1}together with the XOR and the logical AND is a ring. Is it a domain?The power set 𝒫(X) of set X with the symmetric difference (2.4) and the intersection is a ring. Is it a domain? Which subsets are the neutral elements (of sum and product)? Which elements are units?See D.4at page 463

Exercise 2.5Let ℛN×Nbe the ring of N ×N matrices with elements in a commutative ring ℛ. Prove that M ∈ℛN×Nis a unit if and only if detM is a unit of ℛ. Note that since the determinant can be defined using only sum and products, it makes sense to talk about the determinant of a matrix in ℛN×N.

See D.5at page 463

Example 2.3 (Strange example)Polynomials with coefficients in a ring make a ring; matrices with coefficients in a ring make a ring; the subsets of [0,1] with the symmetric difference (2.4) and intersection are a ring. Therefore, the set of matrices whose elements are polynomials whose coefficients are subsets of [0,1] are a ring and I could ask you to compute the determinant of

(2.19)

What is this ring useful for? No clue…

2.2.4 Fields

A field is just a particular type of commutative ring; more precisely, it is a commutative ring where every non-null element has multiplicative inverse. Examples of fields can be obtained from Table 2.1taking the rows where the multiplicative group is x≠0.

Exercise 2.6Why do we require that every non-null element must have multiplicative inverse? What is wrong with zero? Why do we know that zero has no inverse?

See D.6at page 465

Definition 2.5.Let 𝔽 be a field and let 𝔾 be a subset of 𝔽 which is still a field under the operations of 𝔽. Field 𝔾 is said to be a subfield of 𝔽 which in turn is said to be a field extension of 𝔾.