Mathematical Toolkit for TSS. Finite Fields: Introduction
Preface
We begin a series of articles devoted to the algebraic structures used in the TSS protocol.
The first such structure is a finite field.
Finite fields are used in all cryptography, not only in those algorithms that we are interested in, so we’ll talk about them a little more than is necessary specifically for our purposes. In particular, sometimes, we will go a bit deeper into the theory, but not too deep.
Why do we need finite fields?
To begin with, let’s say a few words about why we need finite fields in the first place. Here we won’t try to comprehend any global truth; rather, we’ll just emphasize a couple of things.
Let’s recall the four classic number sets:
All these four sets have certain downsides that make them inconvenient to use as an instrument for computation in cryptography.
For example, natural numbers can not be subtracted and divided — one can get a non-natural number.
Integers can not be divided — one can get a non-integer number.
Rational and real numbers can be subjected to any arithmetic operation, but another problem comes into play here. “Almost all” numbers from these two sets can be represented only as an infinite decimal, e. g.
And when infinite decimals are involved in some computation, roundings emerge, which eventually leads to the accumulation of errors and inaccuracies. And errors and inaccuracies are absolutely unacceptable if we are talking about cryptographic transformations.
In its turn, a finite field is a computing tool, an alternative to numbers. It is a fixed finite set of objects that can be added, subtracted, multiplied, and divided just as we do with numbers. And the result of each operation here is just another object from the initial set.
Finite fields have several significant advantages compared to classical number sets.
So what is a finite field?
Now we will briefly run through all the necessary concepts and terms involved in defining the finite field, and then give the definition itself.
It will be such a super sprint, the goal of which is to concisely show all those things that build the concept of a finite field.
Set
A set is a collection of any objects that are called the elements of this set.
If a is an element of a set A, then we say that a belongs to A and write
If a is not an element of a set A, then we say that a does not belong to A and write
Operation on a set
An operation on a set A is any rule that associates each ordered pair of elements
with exactly one element
Let’s highlight the three most crucial points in this definition.
- An operation associates each pair with exactly one element. So, the same pair can not be associated with more than one element.
- An operation associates each pair with an element exactly from the set where this operation is considered. This condition is called the closure property of an operation.
- In the operation definition, the pairs of elements are considered ordered, i. e., pairs (a, b) and (b, a) are considered different and can be associated with different elements.
Notation for operation
If an operation maps a pair (a, b) to an element
then it is written as a⋆b =c, where “⋆” is a symbol that denotes the operation.
A set A with an operation “⋆” is denoted as (A,⋆ ).
Examples of sets with operations
Our main examples of operations will be addition and multiplication on the sets N, Z, Q, and R. So we get four sets, each with two operations at once: (N, +, · ), (Z, +, · ), (Q, +, · ) and (R, +, · ).
A few properties of operations
Commutativity
An operation “⋆” on a set A is called commutative if a⋆b=b⋆a for all
E. g., addition, and multiplication on N, Z, Q и R are commutative.
Associativity
An operation “⋆” on a set A is called associative if (a⋆b)⋆c=a⋆(b⋆c) for all
E. g., addition, and multiplication on N, Z, Q и R are associative.
Identity element
If an element
has a property that a⋆e=e⋆a=a for any
then e is called an identity element in (A,⋆ ).
E. g., 0 is an identity element in (Z, +), (Q, +) and (R, +). And 1 is an identity element in (N,⋆ ), (Z, ⋆), (Q,⋆ ) and (R,⋆ ).
Invertible and inverse elements
An element
is called invertible if there exists an element
such that a⋆b=b⋆a=e. The element b is called an inverse of a.
E. g., in (N, +, · ) for addition there are no invertible elements at all, and for multiplication only number 1 is invertible — its inverse is itself.
In (Z, +, · ) all numbers are invertible with respect to addition: the inverse of k is − k. And for multiplication, there are only two invertible numbers: 1 and − 1. For 1 the inverse is itself and for − 1 the inverse is −1.
In (Q, +, · ) and (R, +, ·) all numbers are invertible with respect to addition, the inverse for r is −r. In terms of multiplication invertible are all numbers except zero, and the inverse for
Field
A field is a set with two operations
(F, +, ·), where the operations “+” and “·” are called addition and multiplication (these are not those additions and multiplication that we have on numbers, they are just called and denoted the same way) and the following properties hold:
1.The “+” operation is commutative;
2.The “+” operation is associative;
3.There exists an identity element
with respect to operation “+” (this is not the number zero, it’s just the notation);
4. Each element
is invertible with respect to operation “+”, and its inverse is called the opposite or the additive inverse and is denoted as
5. The “·” operation is commutative;
6. The “·” operation is associative;
7. There exists an identity element
with respect to operation “·” (this is not the number one, it’s just the notation);
8. Each nonzero element
is invertible with respect to operation “·”, and its inverse is called just inverse or the multiplicative inverse and is denoted as
9. For operations “+” and “·” holds the distributive property: for any
it is true that (a+b) · c=a · c+b · c.
E. g., (Q, +, · ) and (R, +, · ) are fields, while (N, +, · ) and (Z, +, · ) are not. In (Z, +, · ) point 8 is not met. And in (N, +, · ) — points 3, 4, and 8 are not met.
Finite field
A field (F, +, · ) is called finite if the set F consists of a finite number of elements.
A finite field (F, +, · ) is denoted as
where q is the number of elements in set F. Number q is called the order or the size of the field
We’ve got the definition of a finite field!
In the next article, we’ll discuss what this definition means, cover a few vital properties of finite fields, and approach their concrete examples.
