Division is multiplication by the inverse modulo p, which may be computed using the extended Euclidean algorithm.
A monic irreducible polynomial of degree n having coefficients in the finite field GF(q), where q = pt for some prime p and positive integer t, is called a primitive polynomial if all of its roots are primitive elements of GF(qn).
Now λ51 = 1, so λ is not a primitive element of GF(28) and generates a multiplicative subgroup of order 51.
Having x as a generator for a finite field is beneficial for many computational mathematical operations.
It employs the following reducing polynomial for multiplication: For example, {53} • {CA} = {01} in Rijndael's field because and The latter can be demonstrated through long division (shown using binary notation, since it lends itself well to the task.
Notice that exclusive OR is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.
Multiplication in this particular finite field can also be done using a modified version of the "peasant's algorithm".
This algorithm uses three variables (in the computer programming sense), each holding an eight-bit representation.
This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of a, b, and p and the value 0x1b appropriately.
The multiplicative inverse for an element a of a finite field can be calculated a number of different ways: When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find a generator g and use the identity: to implement multiplication as a sequence of table look ups for the logg(a) and gy functions and an integer addition operation.
This same strategy can be used to determine the multiplicative inverse with the identity: Here, the order of the generator, |g|, is the number of non-zero elements of the field.
[8] When k is a composite number, there will exist isomorphisms from a binary field GF(2k) to an extension field of one of its subfields, that is, GF((2m)n) where k = m n. Utilizing one of these isomorphisms can simplify the mathematical considerations as the degree of the extension is smaller with the trade off that the elements are now represented over a larger subfield.
[10] Here is some C code which will add and multiply numbers in the characteristic 2 finite field of order 28, used for example by Rijndael algorithm or Reed–Solomon, using the Russian peasant multiplication algorithm: This example has cache, timing, and branch prediction side-channel leaks, and is not suitable for use in cryptography.
This D program will multiply numbers in Rijndael's finite field and generate a PGM image: This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.