Implementation of multiplication of polynomials in a finite field
On a foreign stackoverflow I found an example of implementing multiplication of polynomials in a finite Galois field. Help us understand how this algorithm works. Source.
Function code:
/* Multiply two numbers in the GF(2^8) finite field defined
* by the polynomial x^8 + x^4 + x^3 + x + 1 */
uint8_t gmul(uint8_t a, uint8_t b) {
uint8_t p = 0;
uint8_t counter;
uint8_t hi_bit_set;
for (counter = 0; counter < 8; counter++) {
if (b & 1)
p ^= a;
hi_bit_set = (a & 0x80);
a <<= 1;
if (hi_bit_set)
a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
b >>= 1;
}
return p;
}
The mathematical description is simple. The polynomial ring is factorized by the ideal of an irreducible polynomial f, resulting in a set of equivalence classes that consist of polynomials giving the same remainder of division by f.
Mathematical description description of multiplication of Galois field polynomials: multiply two polynomials and take the remainder of the division of the result by f.
We will use only polynomials with coefficients in the binary field, that is, the coefficients of all possible polynomials - zeros and ones. This is convenient for implementation not only in languages, but also in the form of electronic circuits.
In low-level languages, we work with polynomials as with numbers: each polynomial corresponds to a vector of its coefficients, which can be consider it as a decomposition of a certain number in base 2. For example, the polynomial x^4 + x^2 + x + 1 can be matched with its vector of coefficients 00010111, which is the number 23 in the binary system.
Help me understand how what I just described is implemented by this function. It is also very interesting what the hi_bit_set variable is used for, in which the highest bit of an 8-bit number is cut using the 0x80 constant.
1 answers
First, you should understand why it is sufficient to consider polynomials of degree no higher than 7. Therefore, each polynomial can be assigned an 8-bit number. Hence the data type uint8_t.
Consider the main loop. In it, counter is only needed to run the loop 8 times.
for (counter = 0; counter < 8; counter++) {
Then, what happens to b? It analyzes the next bit at each iteration. At first, it is the lowest bit, but at each step, b is shifted to the right by 1 bit, so that b & 1 on the i th is the i th bit of the original number b. (That is, in fact, the coefficient at i-th degree in the second polynomial.)
if (b & 1)
The current amount accumulates in p.
If the current coefficient is 1, p is added to a, shifted (see below) to the left by i units. XOR (^) is equivalent to addition modulo 2 (obviously).
p ^= a;
We store the current upper bit in a (that is, the highest coefficient):
hi_bit_set = (a & 0x80);
And shift a one bit to the left.
a <<= 1;
Thus, in a, the initial value shifted by 1 is obtained at each step (analogous to the i - th line when multiplied into a column). At the same time, we lose the highest bit if it was equal to 1 (because the hash data type is eight-bit, and includes coefficients from 0 to 7 degrees. Now we will make compensation for this.
If the highest bit was set (that is, the coefficient at the eighth power is not 0), we "remember" the factorization and subtract (or something the same (modulo 2, we add) to a the polynomial over which the factorization occurs. At the same time, the coefficient at the 8th power becomes zero, so we again "fit" into our eight-bit data type.
if (hi_bit_set)
a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
End of the iteration. We move on to the next coefficient.
b >>= 1;
}
We see that we just have a column multiplication algorithm.