Numbers and data

Data representing a finite amount of information can always be made "discrete" or "digital".  Humans haven't yet found a way to treat anything else than finite amounts of data, so in principle all pieces of information we can ever obtain or handle, will be able to be represented digitally.  And the specificity of anything discrete and digital is that it can be counted with integer numbers.  All digital data corresponds to a positive integer number.  This trivial fact is at the same time of absolute fundamental importance: any piece of digital data can be represented by an integer number.  The whole content of a 1 Terabyte hard disk is represented by a number which has about 3000 billion decimal digits, but it is a number all right.  Whether you re-interpret that number as 200 films and 7000 pieces of music, or as the catalogue of the bank transactions of Bank A for the last 2 years, is a matter of coding, that is, a mapping between numbers and some or other "more realistic" representation of that data.  But all digital data can be seen as a natural number.

This simple but important fact is what makes the mathematics of natural numbers, which had been a playground for pure mathematicians for centuries, suddenly an important industrial engineering discipline (to the regret of some academics...). 

Seeing information in the form of digital data as "a number" is important in all those aspects where we are considering general aspects of data treatment: of course, most of the time it doesn't make much sense to think of data as "a number" when one is doing domain-specific things.  There's not much sense for someone editing a film to think of that film as a large number: he needs to think of it as "slices of successive images and sound".  But when handling data in general, such as in cryptography, data compression, and the like, the idea that data is just a number is all-important.   If you know the number, you have the data, and if you don't know the number, you don't have the data.

Some mathematicians say jokingly, that god made the natural numbers, and man invented the rest of mathematics.  Others disagree: they say that it was the devil that invented natural numbers.   The mathematical theory of natural numbers is fuller of surprises and traps than any other mathematical discipline.   A lot of cryptography is exactly based upon the mathematical labyrinth of number theory.

One might be somewhat baffled that all data is "just a number".  But we could turn that around: numbers are but a representation of anything discrete, and, we could add, finite.  So maybe it is no surprise that the mathematics of natural numbers is so full of surprises: we are in fact talking about the mathematical properties of all things, finite.

Numbers and groups

The mathematical theory of numbers is studied in primary school, and starts with operations on numbers.  An operation on numbers consists in taking two numbers to produce a third one.  Addition is an operation of natural numbers, and the first thing one learns about mathematics: 2 + 1 = 3.  We take two numbers, here the number 2, and the number 1, and the operation "addition"makes it into a third number, 3.   Addition has a few properties, such as the fact that it doesn't matter in what order we add numbers together: a given finite list of numbers will always add up to the same result, no matter in what order we apply the additions and the numbers, for as long as each number in the list is exactly used once.  A great invention of humankind was the invention of the number zero.  Zero is that funny number that you can add to any other number, and you still obtain the same number.

In fact, zero opens the box of Pandora.  Zero was invented to solve the following riddle: "what single special number can be added to any natural number, so that the result is still that second natural number without change".   In the set of natural numbers: 1, 2, 3, 4,.... actually no such number exists !  One had to invent it: zero !  0.

And now the difficulty is the following one.  Once such kind of riddle is considered, what would stop us from other riddles, such as teachers in first grade are good at asking the children in their class:  "what number do we have to add to 3 in order to obtain 5 ?".  This one is easy: we have to add 2.  The answer is 2.  But if the riddle is "what number do we have to add to 5 to obtain 3 ?", suddenly there's no answer any more in first grade.

The kind of riddle we introduced is the inverse operation of addition: in this case, subtraction.  The first riddle can be written: 5 - 3 = 2.  For the second riddle, we would write 3 - 5 and have no answer in first grade.  There are no apples you can add to a basket with 5 apples, such that you obtain 3 apples.  The question doesn't seem to make sense.

So in as much as addition works on any two numbers, subtraction doesn't.  It works sometimes, and sometimes it doesn't seem to make sense.  Zero was invented to solve the riddle:  5 - 5 = 0, 3 - 3 = 0, 324 - 324 = 0.  With our basket of apples, it kind of still makes sense: "how many apples do you have to add to a basket of 5 apples, to obtain 5 apples ? ".  Answer "nothing at all".  Zero.

And then there's the smart kid in the class that says: "but in order to turn a basket with 5 apples into one with 3, nothing is easier: you eat two apples !".  Indeed.  We considered that the "3" in 5 + 3 = 8 meant "we add 3 apples".  But couldn't we invent another "3" that means "we eat 3 apples" ?  In the same way that we represented "do nothing" by zero ?

Of course.  We call that new version of "3", minus 3.  -3.   To every natural number, we add a new number, "minus".  We have invented a whole lot of numbers now, that didn't exist before:  -1, -2, -3, -4, ....  The entire set becomes the set of integers. 

Now, we can say: 3 - 5 = -2, because 5 + (-2) = 3.   How many apples do we have to add to a basket of 5 to obtain 3 in the end ?  The answer: we have to eat 2 apples.

We can also understand now that 3 - 5 is the same as 3 + (-5), although the meaning is different.  And from that, we can deduce that (-2) + (-3) = -5.

Within our extended set of numbers, subtraction is now always possible.  We have invented enough extra numbers, so that we can now take any two integers, and do the subtraction operation on them, in the same way that we could do the addition operation on the natural numbers and it worked all the time.

It will turn out that being able to have an operation, and its inverse, is so important, that mathematicians have given it a special name: a group.

A group is essentially a set of mathematical objects (such as numbers, but they don't have to be numbers), and an operation (such as addition), so that there is a neutral element (in our case zero), and that the inverse operation is always possible.

The natural numbers with the operation "addition" was not a group.  But by inventing zero, and negative integers, we turned it into a group.  The set of integers and the operation "addition" are a group.  Having a group is important in the sense that a lot of properties have been shown to depend only on the group laws.   So from the moment that the group laws are valid, all these properties are valid.

Numbers and rings

In primary school, addition and subtraction is not the only thing that is learned concerning numbers.  The nightmare of many school kids is to learn by heart the tables of multiplication.   Multiplication is another operation on numbers.  If you take two numbers, say 3 and 4, then 3 x 4 = 12.  Given two numbers, a third number is the result of multiplication.  That's exactly what an operation is.

In the same way as we had the riddle: "what number, added to any other, gives as a result that same other number ?" (and the answer was zero, which we had to invent), we can now consider the riddle: "what number, multiplied with any other, gives as a result that same other number ?".  But this time, we don't have to invent any number, because we have it:  1.  One.  One is the "neutral element" of multiplication.  In the same way as adding zero didn't do anything, multiplying by 1 doesn't do anything.

And in the same way as this opened the box of Pandora to a whole set of riddles, we now have also: "what number has to be multiplied by 4 to obtain 12 ? ", and the answer is 3.   In other words, in the same way as subtraction was a short cut to this kind of riddle for addition, there is an inverse operation for multiplication: division.  We write it: 12 / 4 = 3.   3 is the number that has to be multiplied by 4 to obtain 12.

And in the same way that subtraction didn't always work with natural numbers, division doesn't always work with integers.  If we consider the integers, we actually have two operations on them, addition and multiplication, and two inverse operations, subtraction (the inverse of addition), and division.  The subtraction is "complete", and hence the first operation (addition) forms a group with the integers.  The division is not complete, and hence the multiplication doesn't form a group with the integers.  But there is a relationship between the first and the second operation, called "distributivity":

5 x (4 + 2) = 5 x 4 + 5 x 2 = 30

Now, although the second operation doesn't form a group with the integers, a structure with two operations, where the first forms a group, and the second has a neutral element (one), even though the inverse operation doesn't work all the time, is called a ring.

The arithmetic of integer numbers, with additions, subtractions, multiplications, and division when it works, is a ring.

There is a trick in a ring to make division almost work, which is learned in primary school, and that is "division with remainder", also called Euclidean division.  The concept of division with remainder is one of the important aspects of a ring structure.  A lot of number theory follows from this "division with remainder". In a ring, even though the division itself, as the inverse operation of multiplication, doesn't always work, division with remainder does. Even though 11 / 4 doesn't work for integers (there is no integer, so that when it is multiplied with 4, results in 11), nevertheless, we can say: 11 divided by 4 is 2, with a remainder of 3.  It means that 4 x 2 + 3 = 11.

However, division with remainder is not the inverse operation of multiplication.  In order to make division always work, one has to invent new numbers, so it seems.  The new numbers that are invented to make division work, is the terror of mathematics in primary school (and for some, beyond !): fractions !

If we consider fractions, we have now rational numbers.  In the set of rational numbers (without 0), division always works.  So the set of rational numbers without zero, and multiplication, form a group.  The rational numbers with zero form a group for addition, and the rational numbers without zero form a group for multiplication.  Together, the rational numbers with addition and multiplication, form a field.

A field is great, because every operation can be inverted. 

But we wanted to keep integers in data treatment, because all data could be represented with integers.  We can't do much with fractions.  Nevertheless, fields are important in data treatment, because we want to be able to treat data, and get the original back, so we have to be able to do all inverse operations.  What we need are integer numbers that form a field.  With the classical integers, classical addition and multiplication, we can't get more than a ring.  But there is a solution.  There is a way to get a field with integers !

Cyclic groups modulo n.

When subtraction failed, people invented new numbers, namely the negative numbers, to make subtraction work again.  But there's another trick that works also, and that is: consider only a finite set of numbers, and consider them "on a circle" instead of "on a line".  Addition is then "moving clockwise", and subtraction is "moving counter clock wise". 

Consider only 6 integers: 0 - 1 - 2 - 3 - 4 - 5.     In that small set of integers, we can of course define addition, up to a point, as "normal addition": 2 + 1 is still 3. Two plus two is still 4.  However, how much is 4 + 3 ?  If we apply the procedure, it means: "start at position 4, and move 3 positions to the right".  So we have: 4 - 5  - 0 - 1.  4 + 3 equals 1. 

Now, it is clear that such kind of arithmetic cannot be used if integers represent "a count of physical objects".  If you have 4 cows and you add 3 cows, you don't have one cow !  But we're not considering numbers here as representing "an amount of physical objects".  We consider numbers as "data".  The very big number that represents a movie (a number with about 2 billion decimal digits) doesn't represent a number of physical objects, but just "data".  In as much as we will transform "data" by doing calculations on that number, to make other numbers, we care actually more about the reversibility of the operation, rather than the fact that the number represents "a number of physical things".  Indeed, the reversibility of the operation means that we can get the original data back, and that's what counts, be it in cryptography or in most other general data manipulations.  So in as much as 4 + 3 = 1 doesn't make any sense in counting objects, it can perfectly make sense to say "the data represented by the number 4 is now represented by the number 1".   As long as we can get back.  And we can.   1 - 3 = 4 !

Indeed, consider 1, and apply the prescription: "subtracting 3" means: going back 3 steps.  So we have: 1 - 0 - 5 - 4.  1 - 3 is indeed 4.

The addition, thus defined on this finite set of numbers in a cyclic way, forms a group. 

So instead of inventing more numbers, we could also restrict the amount of numbers to a finite amount, and addition could be turned into a group.  But it is not addition that corresponds to "adding a number of physical objects together" any more.

In fact, this group has a strong relationship with the remainders in Euclidean division: the resulting element is obtained by doing the normal addition or subtraction with integers, followed by a division with remainder by the number of elements in the cyclic set.  The remainder is then the result:

If we have, in our group with 6 elements, the addition 3 + 4, we perform the normal addition, that is to say, 3 + 4 = 7, and then divide by 6 with remainder.  7 / 6 = 1 with remainder 1.  So 1 is the answer: 3 + 4 = 1.  It turns out that subtraction works in fact the same way.  This didn't have to be the case, but it is: if we calculate normally 1 - 3 we find -2.   The Euclidean division of -2 by 6 gives us -1 with a remainder of 4 (indeed, -1 x 6 + 4 = -2).

In the same way, we can consider the multiplication in this set:  3 x 4 = 12, and 12 divided by 6 has remainder 0, so we have: 3 x 4 = 0. So we have defined also a multiplication on this cyclic set.

But the inverse operation, division in the cyclic set doesn't always work.  In this case, for instance, if we cannot divide 0 by 4 to obtain 3 because 0 x 4 also gives 0.  So dividing 0 by 4 would have to give two answers: 0 and 3.  Moreover, there is no "trick" with normal division and taking the remainder by dividing by 6 to imitate the division in a cyclic set.

It turns out that for most cyclic sets (that is, for most n where we consider the cyclic set with n elements), the set equipped with cyclic addition, and cyclic multiplication, is a ring.

However, there is a particular property when the number of elements in the cyclic set is a prime number.  Indeed, in that case, the division is always possible !  Let us consider the cyclic set with 5 elements (5 is a prime number).  The multiplication table looks like this:

x 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2  1

As one can see, apart from the row and column containing 0, every row, and every column contains exactly once all non-zero elements.  This is the necessary condition to "go back" of course: if all the non-zero elements in the set appear exactly once in each column (and hence also in each row, as the table is symmetric in rows and columns), it means that "multiplying with the column head" can generate every single non-zero element in the set by multiplying it with the corresponding row head.  As such, every single non-zero value in the set can be divided by the column head, and the result of the division will be the row head.

If we want to divide, say, 3 by 4, we look in the column of 4 where 3 occurs.  It occurs in the row with 2.  So 2 is the result of the division of 3 by 4.  Indeed, 4 x 2 = 3 (4 x 2 = 8 with normal multiplication, and the remainder when dividing by 5 is 3).

This is a single most important property:

In the case the number of elements in the cyclic set is a prime number, the set, with addition and multiplication, is a field.

Now this is interesting: we have a field with integer numbers.   We didn't have to invent fractions for that, after all.  Of course, the price to pay is that the addition, and the multiplication, do not correspond to what happens with "amounts of physical objects".  But remember that we are considering numbers here as "data".  We can transform data (represented by a number in a cyclic set with a prime number of elements) into other data, and back, using additions and multiplications in this cyclic field.

We also saw that in a cyclic field with p elements (where p is hence prime), multiplying 0, 1, 2, .... , p - 1 with any non-zero constant results in a re-arrangement of these elements, where each of them occurs exactly once.  From this follows Fermat's Little Theorem:

For every integer a which is not divisible by the prime number p, we have:  ap - 1 = 1 in the cyclic field.

There is a slightly more general formulation of Fermat's Little Theorem:

For every integer a, and every prime number p, we have that ap = a mod p.

Finite fields

Remember that a field is a set in which there are two operations (which we usually call addition and multiplication) so that their inverse operations (subtraction and division) are always defined (except the division by zero).  It also means that there are two neutral elements: "zero" for the addition, and "one" for the multiplication.  One calls the character of a field, the number of times one can add to itself "one", so as to give "zero".  If that never happens, one says that the character of the field is zero.  In our cyclic field with p elements, the character is in fact p.  Indeed, if one adds 1 + 1 + ... 1, p times, then one obtains 0.  Our cyclic fields are special, in the sense that the number of their elements is equal to their characteristic.

One can in fact show that any finite field with q elements and characteristic p, must have that q is a power of p.  In fact there is only one single field (up to equivalence of course) for every prime p and every power f, such that the number of elements in the field is q = pf.  When f = 1, this field is the cyclic field we mentioned, and when f is larger than 1, it can be represented by an f-tuple of elements from the cyclic field.  In other words, by studying the cyclic fields of p elements, we have studied in fact all finite fields.

A finite field is composed of two finite groups: there is the additive group on the basis of all the elements of the field, and the addition operation, and there is the multiplicative group on the basis of all of the elements of the field except for the zero element of addition, and the multiplication operation.  In what follows, we will actually consider this multiplicative group when considering the field.  That is, we will be talking of the generator of the field, but in fact, we are talking of the generator of the multiplicative group of that field.

Field (and group) generators

If we have a finite group with an operation which we call "multiplication", then, multiplying an element a of the group, with itself a certain number of times, say, n, is taking the power of that element: ap = a x a x .... a (p times).

In fact, if we consider, in a cyclic field, the additive group, then what we call "power" is in fact multiplication, because, say, 5 x a is nothing else but a + a + a + a + a.  But we consider here the multiplicative group mainly.

If there are q elements in the group (remember that the multiplicative group of a field has one element less than the field itself: zero is not part of it !), and we take an element of that group, a, then we can consider all consecutive powers of a:

a ; a x a ; a x a x a ; a x a x a x a ; and so on.  Of course, the group not having more than q elements, sooner or later in this series, two results will have to be the same: an = am.  Dividing by the smallest of both powers (say, m), we find then that: a(n - m) = 1.

In other words, this sequence of successive powers of a has to include "1" at a certain point.  The first occurrence, the smallest power of a that gives 1 as result, is called the order of the element a.

It is obvious that the order of an element can never be larger than q, the number of elements in the group.  In fact, the order of an element has to be a divisor of q.

Consider the cyclic field with 5 elements (5 is a prime number).

Consider its multiplicative group (which has only 4 elements): 1, 2, 3 and 4.

The order of 1 is 1, because 11 = 1

The order of 2 is found as follows: we have as successive powers of 2: 2, 4, 3, 1.  So the order of 2 is 4.

The order of 3 is found as follows: the successive powers of 3 are: 3, 4, 2, 1.  The order of 3 is 4.

The order of 4 is found as follows: the successive powers of 4 are:  4, 1.  The order of 4 is 2.

We see that we have one element with order 1, one element with order 2, and 2 elements with order 4.

A generator of the group (and in case of the field, of the field) is an element of the group or field, such that its order is equal to the number of elements of the group.  This means that all the elements of the group can be written as a specific power of that element.

We also see why there's no point in looking at that for the additive group in a field.  Indeed, the additive group in a field has all the elements of the field (including zero) and hence the number of elements in the group is the number of elements in the field, which is a prime number.  This means that the order of the elements (in this additive group) should be a divisor of this prime number, hence, the prime number itself, or one.  Zero has of course order one under addition, and all other elements have order p.  All non-zero elements are generators of the additive group.  This is why we concentrate on the multiplicative group if we have a field.

It can be shown that every group (and field) has at least one generator.

Generators are important, because a generator of a group allows one to introduce a permutation of the elements of a group (or field) which is highly non-trivial.  Going back to our data: consider that our data is a number d in a finite field (with p elements, where p is a prime number, which can be very large).  Now, consider that we have chosen the number a as a generator.

We can consider f = ad as a transformation of the data into other data, represented by the number f.  The relationship between f and d is highly non-trivial.  In fact, in as much as it is easily done to find f if we have d, in most cases, there's no way to easily recompute d if we have only f.  We will be interested in such "one way" computations in cryptography for instance.  This problem is called "the discrete logarithm" problem, because going back from f to d, implies taking the discrete equivalent of the logarithm in base a, of f.

In a field, the additive group clearly is no good candidate for the "discrete logarithm problem", because the "logarithm" of an additive group is simply division, and in a field, the division is not difficult to execute, so there is no "discrete logarithm problem" in the additive group of a finite field.   This is why the cryptographic applications of finite fields concentrate on the multiplicative group, and not on the additive group.

The polynomial ring

On every ring, one can construct a polynomial ring.   The ring we started with is called the base ring.  That base ring can be a ring, or a field.  It is, as any ring is, made up of a set (we will call this set B), and two operations, which are traditionally called addition and multiplication.

A polynomial over the ring B,+,x is a function from B into B, for which the prescription is given by a polynomial formula:

f(b) = A0 + A1 x b + A2 x b2 + A3 x b3 + .... + Am bm

where A0, A1, ... Am are also elements of B.  Given that B is a ring, the above operations are always possible, so the function is defined over all of B.  The polynomial is totally defined if we know the coefficients.  The highest power of the argument is called the degree of the polynomial.

The set of polynomials themselves is written B[X].  It can be represented by all tuples of elements of B: (A0, A1, A2... Am).

The polynomials themselves can be added together, and one can multiply polynomials.  The results are again, polynomials.  Subtraction of polynomials is always possible, and there is a "zero" polynomial: the polynomial with all coefficients zero.  Indeed, adding this polynomial to a given polynomial, doesn't alter this polynomial.  There is also a "one" polynomial: the polynomial with all coefficients zero, but for the constant term (A0) which is equal to 1.  In certain cases one can divide a polynomial by another one, and obtain a polynomial again.  However, in many cases, this division is not possible.  But the division is always possible if we consider a "remainder".  As such, the set of polynomials, equipped with a polynomial addition, and a polynomial multiplication, is a ring.

B[X], + x is a ring.

Although polynomials can be defined over a base ring, it becomes much more interesting when they are defined over a base field.

Indeed, in a finite field with p elements (where p is a prime number), we know that the highest order of any element is p - 1 (and that such elements are present: the generators of the field).  As such, polynomial functions cannot be of higher degree than p - 1, because a term with any higher power would reduce to a lower power.  A term with a power, say, of p + 1, would reduce to a power of 2, so this polynomial would be entirely equivalent (as a function) to a polynomial in which this term Ap+1 bp+1 were absent, and Ap+1 was simply added to A2 .

This is in fact a direct consequence of Fermat's Little Theorem in its more general formulation: Xp = X in B.

As such, the set of polynomial functions will be limited in degree, and the representation by tuples will contain at most tuples of length p.  As every coefficient can only take on a finite amount of values (all the values in the base field), and there are only p such coefficients, B[X] seen as polynomial functions is a finite ring.  Of course, nothing stops you from considering the formal expressions of higher order than p-1.  But as functions from B to B, these higher-order polynomials don't make sense.  In many cases, B[X] is seen as the ring of formal polynomial expressions, and not as polynomial functions.  In that case, B[X] remains unbounded.

A monic polynomial is a polynomial where the coefficient of highest power is 1.  Every polynomial can be seen as a constant (an element of the base field) and a monic polynomial (because the division is well-defined in the base field - this doesn't work for a base ring).

A monic polynomial is called irreducible (or a prime polynomial) if there doesn't exist any other monic polynomial (that is non-trivial, that is, not equal to 1) that divides it.

Every monic polynomial can be written as a unique product of irreducible polynomials.

We see that irreducible polynomials have a role somewhat similar to prime numbers in the ring of integers.

Let us illustrate this with the finite base field {0, 1, 2}:

There are 27 possible different functions over this base field, so there cannot be more polynomials (as functions).  Indeed, any function has 3 possibilities to map 0 to, has 3 possibilities to map 1 to, and has 3 possibilities to map 2 to.

There are 27 possible polynomials up to degree 2:

p(x) = 0;  result on {0, 1, 2} is {0, 0, 0}

p(x) = 1; result on {0, 1, 2} is {1, 1, 1}

p(x) = 2; result on {0, 1, 2} is {2, 2, 2}

are the 3 possible polynomials of degree 0.

p(x) = 0 + x ; result: {0, 1, 2}

p(x) = 1 + x ; result {1, 2, 0}

p(x) = 2 + x : result {2, 0, 1}

p(x) = 0 + 2 x ; result {0, 2, 1}

p(x) = 1 + 2 x ; result {1, 0, 2}

p(x) = 2 + 2 x ; result {2, 1, 0}

are the 6 possible polynomials of degree 1.

p(x) = 0 + x2 ;  result {0, 1, 1}

p(x) = 1 + x2 ; result {1, 2, 2}

p(x) = 2 + x2 ; result {2, 0, 0}

p(x) = 0 + x + x2 ; result {0, 2, 0}

p(x) = 1 + x + x2 ; result {1,0, 1}

p(x) = 2 + x + x2 ; result {2, 1, 2}

p(x) = 0 + 2 x + x2 ; result {0, 0, 2}

p(x) = 1 + 2 x + x2 ; result {1, 1, 0}

p(x) = 2 + 2 x + x2 ; result {2,2,1}

p(x) = 0 + 2 x2 ; result {0, 2, 2}

p(x) = 1 + 2 x2 ; result {1,0,0}

p(x) = 2 + 2 x2 ; result {2,1,1}

p(x) = 0 + x + 2 x2 ; result {0, 0, 1}

p(x) = 1 + x + 2 x2 ; result {1, 1, 2}

p(x) = 2 + x + 2 x2 ; result {2, 2, 0}

p(x) = 0 + 2 x + 2 x2 ; result {0, 1, 0}

p(x) = 1 + 2 x + 2 x2 ; result {1, 2, 1}

p(x) = 2 + 2 x + 2 x2 ; result {2, 0, 2}

are the 18 possible polynomials of degree 2.  We see that we have also exhausted all possible functions from B to B.

But of course, one can consider formally, polynomials of a higher degree.  However, these "polynomials" shouldn't be considered then as functions over B, but just as tuples of elements of B, whose composition by addition and multiplication behaves as if they were coefficients of power terms in a polynomial expression.  Under this more abstract addition and multiplication of tuples, one can define irreducible tuples, Euclidean division of tuples and so on.  This ring of abstract tuples, which can formally be seen as polynomial expressions, is not finite, as the degree can be arbitrarily high.

In fact, this is the formal mathematical way to define B[X]: this ring is not seen as polynomial functions from B to B, but rather as the ring that results when one extends the ring B with an extra element, called X.  In order for this extension to be indeed a ring, one needs to have now the set of all possible linear combinations of the elements of B, and all possible powers of X.  That's exactly what these formal polynomial expressions represent.  So one can think of B[X] as the extended ring that contains B and an extra element, "X".

Field extensions

Consider a cyclic field with p elements, which we will call Fp.  Consider now the ring of (formal) polynomials over this field: Fp[X].  This is a ring, as said earlier, and in a ring, there is Euclidean division, and hence there are irreducible polynomials, which play a similar role in this ring, as prime numbers do in the ring of integers.

Let us remember how we obtained a finite field from the ring of integers: we considered the set of remainders after division by a prime number.  Indeed, we can see Fp as the field that results when we consider all elements of the integer ring, modulo p.

We will now apply the same trick to the ring of formal polynomials over Fp[X].  Indeed, let us pick a particular polynomial P(X) in Fp[X], such that P(X) is an irreducible polynomial, and consider now the following set:

Fp[X] / P(X), or in other words, the set of all polynomials that are remainders when dividing all polynomials in Fp[X].

It turns out that Fp[X] / P(X) is a finite field, with addition and multiplication "modulo P(X)".

If the irreducible polynomial is of degree m, then the resulting field will have pm elements.  It is one of the practical tricks to make finite fields with non-prime numbers of elements.  Galois demonstrated that we can find all finite fields this way.

As an illustration, the famous AES encryption standard, at a certain point, uses the field based upon F2 and the irreducible polynomial f(X) = X8 + X4 + X3 + X + 1.  This makes a field with 28 = 256 elements.  This was done for practical reasons, in that an element of this field can be represented by a single byte.

We can now close the circle: the relationship between the polynomials seen as "function from B to B", the "formal polynomials using an extra element X" and the quotient set (the set of remainders) B[X]/P(X) is the following:

If we take as "divider polynomial"  Xp - X(which is of course never an irreducible polynomial, because it can be divided by (X - 1) and by X), and we construct the quotient set:

Fp[X] / (Xp - X)

then we obtain exactly the same polynomials as remainders, as the set of polynomial functions.  As Xp - X is not an irreducible polynomial, however, the resulting quotient set will not be a field, but rather a ring.

The ring of function polynomials over Fp is obtained by taking the quotient ring Fp[X] / (Xp - X).

In our example, we had the base field F3.  Taking the quotient set (taking the set of remainders after division) of the polynomials modulo X3 - X comes down to adding the coefficient of X3 to the coefficient of X and eliminating the power of 3, adding the coefficient of X4 to the coefficient of X2 and eliminating power 4, etc... which is exactly what we have when we consider these as power functions over F3.

In other words, a polynomial 2 X4 + X3 = 2 (X4 - X2) +2 X2 + X3 - X + X = 2 X (X3 - X) + (X3 - X) +2 X2 + X and after dividing by (X3 - X) and taking the remainder, only 2X2 + X remains.  One can ask where the -X comes from.  It is in fact another way of writing 2X in F3 of course, to make things more visible.

Finally, it can be interesting to note that the quotient field (or ring) Fp[X] / P(X) and the quotient field (or ring) Fp[X] / Q(X), where P(X) and Q(X) are polynomials of the same degree m, are the same sets: namely all polynomial expressions with coefficients in Fp up to and including degree (m - 1).  It is only the multiplicative law which is different over these sets.

The addition is not affected, because adding two polynomials of degree at most (m - 1) will result in another polynomial of degree at most (m - 1), and hence its quotient when divided by a polynomial of degree m will always be zero: the polynomial of degree (m - 1) will be its own remainder. 

Let us illustrate this with our F3 example, and we take two polynomials of degree 3.  In that case, the resulting set will always be the set we have enumerated earlier on: the 27 polynomial expressions up to degree 2.

Let us take as P(X), the polynomial X3 - X, leading to the "function polynomial" ring.  Let us take as Q(X), the polynomial X3.  Note that we took two polynomials which are reducible, so we won't obtain fields.  We just illustrate the concept with as simple an example as possible.

Let us now consider two elements of the polynomial set:

p1(X) = 2 X + 1

p2(X) = X2 + 1

In the first ring (modulo P(X)), the product of both becomes:

p1(X) p2(X) = (2 X + 1) (X2 + 1) = (2 X3 + 2 X + X2 + 1) mod P(X) which results in: X2 + (2 + 2) X + 1 = X2 + X + 1.  The (2 + 2) X comes from the original term 2 X, and the coefficient 2 of X3 which is reduced to a first order term by the remainder operation (or by Fermat's Little Theorem in this case).

In the second ring (modulo Q(X)), the product becomes:

p1(X) p2(X) = (2 X + 1) (X2 + 1) = (2 X3 + 2 X + X2 + 1) mod Q(X) which results in X2 + 2 X + 1, because the remainder function here simply sets all coefficients of X3 and higher to zero without transforming them into lower-degree contributions.

So we see that the product of two polynomial expressions has two different results in the two rings: in the first ring, p1 x p2 = X2 + X + 1, and in the second ring, p1 x p2 = X2 + 2 X + 1.

Let us check that the first ring does correspond to polynomial functions and the second ring doesn't.  The multiplication of two functions has to be such, that the resulting product function gives an image for every element in F3 such that it is equal to the product of the images of that element under the two functions of which we're calculating the product.

In other words, if p3 = p1 p2 and p1, p2 and p3 are considered genuine functions over F3, then for every a in F3 we have to have that p1(a) = b1, p2(a) = b2 and p3(a) = b3 such that b3 = b1 b2

Is that so ?

{0, 1 and 2} under p1 gives us {1, 0 and 2}

{0, 1, and 2} under p2 gives us {1, 2 and 2}

The product of these images is {1, 0, 1}.

Does this correspond to p3 we have found under the multiplication law of the first ring ?  In fact, the polynomial that corresponds to the above images is indeed X2 + X + 1 as we found there.

It is not the polynomial X2 + 2 X + 1 which is the result in the second ring, and which, if interpreted as function over F3 would have given the images {1, 1 and 0}.

 Conclusion

As all digital data, and by extension, all information one can handle, can be seen as a natural number, general transformations of data (without reference to their particular interpretation and meaning) such as used in cryptography are transformations of natural numbers.   In order to have useful transformations that can go back to the original data, one needs reversible operations on natural numbers.  The standard additions and multiplications we learn in primary school are not reversible as such.  We have seen how we can construct additions and multiplications on finite sets of natural numbers which are reversible and behave up to a certain point like the normal addition and multiplication.  Such a structure is called a field.  The base construction is the cyclic field Fp where p is a prime number (if p is not a prime number, multiplication is not reversible and we don't have a field).  We have seen how to construct more involved fields on n-tuples of natural numbers, interpreted as formal polynomials over these cyclic fields.  They have pn elements, and are constructed by taking the quotient field of the (infinite) ring of formal polynomials over Fp, namely Fp[X], and an irreducible polynomial of degree n.

In doing so, we have in fact constructed representations of all existing finite fields.  Galois demonstrated that there are no other fields than those.  Having constructed them using a finite set of integers, or a tuple of finite set of integers, we can actually perform all calculations in any such field, provided we can:

  • do additions, subtractions, multiplications and divisions in Fp
  • do additions, subtractions, multiplications and divisions in Fp[X]/P(X)

Fields are somewhat of a luxury: we actually only need one reversible operation to "do things on data and get back".  As such, finite groups can also be of interest.  Of course, we already have a lot of interesting finite groups: the multiplicative groups of the finite fields we just mentioned.  However, if we restrict ourselves to groups, there are more possibilities than just the multiplicative groups of finite fields: there are groups that cannot be part of a field.  However, practically, we want these groups to be represented by natural numbers of course, so the groups we are potentially interested in, will be constructed inside a finite field.