Finite Fields and Their Applications

Hello, my name is Adam Strabojinski, and today I will be talking about finite fields and their applications. So the finite field functionality has been introduced in Mathematica version 13.3, and some of the functionality I'll be talking about today is going to be added in version 14. So first we have functions for representing finite fields. It's finite field and finite field elements. Then we have finite field operations. So arithmetic functions plus times integer power, finite field element trace norm primitive Q, minimal polynomial and multiplicative order work with finite field elements. Then we have finite field mappings. These are two functions. Frobenius automorphism and finite field embedding. Then conversion utilities. This is something that will be added in version 14. Functions to finite field and from finite field for converting coefficients of rational functions to finite field and from finite field elements and finite field index and from finite field index for converting indices to finite field elements. Then we have functions for polynomials over finite field. So all those polynomial transformations work for polynomials with finite field coefficients. And this has already been implemented in version 13.3. And then there are two things that are added in version 14. One is linear algebra over finite fields. So now all those linear algebra functions work for matrices of finite field elements and equations over finite fields. So solve, reduce, resolve and find instance work for equations with finite field coefficients. So let me start with describing finite field representation. So a finite field is represented by by finite field with argument P, which is a prime F, which is a polynomial function irreducible over zp and rep, which indicates the representation used for finite filaments. It's either polynomial or exponential. So P is called the characteristic of the field, F is called the irreducible of the field, and the degree D of F is called the extension degree of F Zp. And the field FF has P to the power d elements, and the elements are indexed by integers between 0 and p to the power d minus 1. So for instance, this will construct the finite field with 17 to the power three elements. This gives the element with index 123. See, it's how it's displayed. You can click here and see the finite field. And you can click here and see explicitly the characteristic extension degree, the field irreducible, and it's a polynomial representation. If we don't specify representation, it will use polynomial representation and this can be collapsed. And so field elements are represented by atomic finite field objects. So this object has had finite field elements, but it's an atomic object, you cannot extract parts of it. To learn the information about it, you have to use the information function, you cannot extract part directly. So elements of F can be represented as polynomials of degree at most D minus 1 in the field generator. The field generator is a root of the field irreducible and. So every element of the field can be defined by giving or specified by giving a coefficient list of a polynomial in theta. So for instance, this is the element specified by this coefficient list. And here is the information we can extract information about the field. So characteristic feeder, reducible field size. Here's the number of elements field size, right this element information about the field element. So this gives the index of a. See a was here the 1, 2, 3. And this gives the field in which it is an element of and element can be the index of a field element can also be extracted this way by evaluating a of index. So now let me discuss shortly the two representations that we have. So in the polynomial representation, the field element is represented as a polynomial in the field generator, and the index is computed by using the polynomial coefficients as digits with base p. So for instance, if we extract this element with this coefficient list, then index will be the coefficient list.powers of 17 of the characteristic. See, we got the index 20, 11, and to find the coefficients from the index we do reverse integer digits base 17 and we got 357 back. And the other representation is exponential representation. So this constructs the field with 23 to the power four elements in exponential representation. So in the exponential representation, the field irreducible is always chosen to be a primitive polynomial. Hence each non zero element of the field is is a power of the field generator. So the index of the kth power of the field generator is chosen to be K +1, so that the index of this field 0 is always 0. 0 is of course not the power of the field. All the non zero elements are powers of the field generator and so and the index of 1 is also always 1, so it's both. In exponentially polynomial representation, field 0 and field 1 are represented by indices 0 and 1. So this gives us the field generator, right? It's 0 times it's a constant terms plus 1 times the field generator. So we can always get the field generator this way. Here is the power 123 of the field generator, so it has index 124. And here we add fifth and seventh power of the field generator. And this is a number we can easily compute from this. This is computed using a table of logarithms. And of course each element C can be represented as a polynomial of each integrative degree at most d. So we can find coefficients even in the if the field is generated is represented in the exponential representation. So why do we have these two representations of the exponential representations provide somewhat faster field element arithmetic than the polynomial representation at the cost of pre computation that's necessary when the field is created. So the pre computed table of sec logarithms has size proportional to the number of field elements. Hence the exponential representation that cannot be used for two large fields. So we can use exponential representation if the number of field elements is less than a billion. So if we take a field with more than billion elements, finite field will not construct the exponential representation. We can still construct this field in polynomial representation. This field has 11 to the power 10 elements. So let's now talk about finite field operations. So we take the finite field with seven to the power five elements, take two elements of this field, do some arithmetic. So we can do addition, multiplication powers, division. Here it goes. Integers and rational numbers valid modulo P are automatically treated as field elements. So we can add three to a field element. We can compute some field element properties. So this computes the trace or the sum of all conjugates of the elements. This computes minimal polynomial of the elements. This computes the multiplicative order that's quite, quite high. This is a large field, reasonably large. Now, finite field mappings. So the free penins atomorphism is given by raising the element to the power p. This gives an automorphism in in a finite field with characteristic p. And all automorphisms of the finite field are powers of the Frobenius automorphisms. And the first d powers are different. So we have d different automorphism of a field with extension degree D. So here is a finite field with extension degree 4. Here are two elements, and we can verify on those two elements that Frobenius automorphism is indeed an automorphism. So it preserves addition and it preserves multiplication. And this finds all conjugates of an element of the finite field. So you can see the fourth power of the Frobenius automorphism is is the identity already. So we have four different automorphisms in the finite field of extinction degree four. And well, since these are well, the conjugates of field elements are all the roots of the minimal polynomial of this element. So they will have all will have the same minimal polynomial. So now let's construct a larger field, so same characteristic, but three times larger extension degree. So now the field FF is isomorphism to a subfield of the field gg, but it's not automatically considered a subfield of gg because there is no standard embedding of FF in gg. There are three different embeddings. So we cannot add element of the smaller field to an element of a larger field, but we can construct an embedding of the field ffgg. This is a specific embedding which sends this element of the first field to this element of the second field. And now we can embed element A in the larger field. And now we can add it to an element of the larger field. And appendix, preserve field operations we can again check on the two elements that we have now. Let's talk about polynomials over finite fields. So we generate a finite field, just have two elements of this finite field. So we can factor polynomials over the finite field. We use the extension option to specify the field. We could have used here finite field elements coefficients, but we can use integer coefficients. They are automatically embedded in the finite field. And we get the factorization. So this polynomial factorizes into linear factors over the field. This computes a polynomial remainder over the field. This computes a discriminant. And this cancels x minus a divided by minimal polynomial of x. So this should be a factor in this minimal polynomial. So and it did. Yeah, it was cancelled. Okay, now for converting the coefficients. So this is something new in version 14. So we have polynomial with integer coefficients. We want to convert it to polynomial with field coefficients. So remember, this was the field with characteristic 19. So 21 got converted to 2 and 37 got converted to 18. Now we factor this polynomial and we can convert the the factors where the field elements are converted to polynomials in T. So the T standing for the field generator. So instead of having a polynomial with field coefficients, each coefficients in the field gets converted to explicit polynomial in the field generator where the field generator is represented by the specified variable. So we can expand it, collect it with respect to x, and then convert it to finite field. And we should get and do get the same polynomials here. Now, linear algebra over finite fields. This again is something new in version 14. So first, well, we generate a random matrix of elements of finite fields. Here we use the new function from finite field index, so we can generate random integer matrix. And now this will convert all the integers to field elements with those indices. So we have random matrix of field elements. Now we compute inverse of the matrix, check that it's actually an inverse. So we got a identity matrix over the field. Now we compute matrix power. You can see that we can compute really large powers because we are in the finite Field so the elements will not keep getting larger and larger. And. This is a random vector of field elements. And we can solve linear equation using the matrix and the vector Here is the solution. And we can check that indeed it is a solution of the linear equation. We got zero. Okay, now equations over the finite field. So again we have some finite field. Now we solve univariate equation polynomial equation over the finite field. These are the two roots that this fourth degree equation has in this particular field. Or we can use field as the domain argument of reduce. So the polynomial had integer coefficients. But we specify that we want a solution over the field and here are the solutions. And here's a solve with the system of polynomial equations. We get the solutions and here's findinstance. So we have one equation, three variables, but we just want one instance solution of this equation. Okay, now for applications, finite fields are used in algebraic computation, error correcting codes, cryptography, combinatorics, algebraic geometry, number the array and finite geometry. So I'll give a sample 2 applications. There are more applications in in the documentation in version 14. So first, how to implement a Diffie Hellman public cryptosystem with 129bit prime. So we generate the 129bit prime and the finite field. So this is a prime field. Actually, if we don't specify the extension degree, we get the prime field with p elements. Find the primitive element of the field using the primitive root function. It's a prime field. So now how this thing will work, Basically both the person sending information, the person receiving information, they pick some number between 2 and P minus 2 and they publish the field, the generator of the field and the power of the generator. But they keep this number, the number A. The first user keeps his number a secret. And the security of the cryptosystem is based on the fact that it's really hard knowing G and knowing G to the power A. It's really hard to compute A. So. Okay, what happened here? Oh, okay, I didn't evaluate. Okay, didn't evaluate this line. So we pick a random integer A. Now we evaluate G to the power A and we get a field element that the first user is publishing. Now the second user again chooses his secret integer and to send an encoded message, M128 bit message. So it's again the message will be an integer. The user sends m multiplied by g1. So the thing that the first user sent to his raised to the power B and he publishes G raised to the power B. Again, it's difficult to compute B knowing G to the power B and G. So this is secure to send those things. So now both the first and the second user can knows what G to the power A times B is. But nobody can figure out what G to the power a rigid power B is, nobody who is watching the conversation. And the first user can recover M by computing E divided by G2 to the power B to the power A other known as G to the power A times B. So we compute this and we check that the index of this element is indeed the message that was encoded. So that's how the Diff Hellman cryptosystem works. The second example is side onsets. So the FI set of integers is a sit on set if the sums of AI plus aj for all pairs I and J are all distinct. So for instance the set Of Powers of 2 is a sidden set in the interval 1 and 2 to the power n minus 1. But you can see the sedan set has the interval has exponential size compared to the size of the sedan set. And we will try to construct a Sedent set with as many elements in as small intervals as possible. And so we can have a sedan set of Q integers in interval of 1 through q squared minus 1. So it's only quadratic in size, not exponential in size as it is in here. But we can do it for prime power Q. And if you look at the code, the set of elements of the season sets are exponents K such that G to the k minus G where G is generator of the field belongs to the Q element subfield of F. This is the fact that this that such set must be a Sedon set is somewhat easy to prove. It's not completely obvious, but it's rather easy proof. But here we just. Well, for some specific Q7 squared we generate a sedoncet with Q elements, check that it really has Q elements, and we can check that all the sums are indeed distinct. So this concludes my talk. Thank you very much for listening. And now let me look if there are any questions. Okay, I'm back. Now I see that there are some questions. So is the performance of operations better on finite fields better than the non integers? Not quite sure, but it's pretty fast. It's comparable to the operations on integers. Solving a polynomial system uses factorization to get roots in the finite fields. It's somewhat more complicated. So we first reduce the degree of the polynomial and then factorize it. I think that's how it works, better than calculating modular P. Okay, well, I haven't actually tried to compare the arithmetic performance, so that's something to check. I would expect it to be at least equally fast. Can I recommend a book on finite fields? Let me see. So I right here I have two books with me, which is Finite Field with Application to Combinatorics by Canons Sundararajan and Finite Fields and Application by Mullen and Mamert. So these are small books. And there is also one very popular book which I. Well, I don't really remember the authors. So let me see, maybe I'll find on Amazon. Okay, so here I sent a link to rather popular textbook on finite fields. It has a lot of information. That's a pretty good definitive book on finite fields by Lidl and Niederriter. Okay, so I think there are no more questions. So I will finish the talk then.