# Multiplication over the binary finite field GF(2^m)

The `multGF2()` function shown in the Python script below implements the element (polynomial) multiplication over a binary finite field $GF(2^{m})$. The second function, `setGF2()`, sets the three constants needed for its colleague to perform its multiplication task: `"mask1"` and `"mask2"` (used in “and” operations) and `"polyred"`, a polynomial constant used in the polynomial reduction of the product. These constants are defined from the parameters passed to `setGF2()`: `"degree"` (the extension degree of the binary field $GF(2^{m})$) and `"irPoly"` (the irreducible polynomial used for the product reduction). The version of `multGF2()` in the post AES implementation in Python, dubbed “`mult()`“, was configured specifically for the AES binary finite field used in the MixColumns operation, $GF(2^{8})/x^{8} + x^{4} + x^{3} + x + 1$.

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Binary finite field multiplication in Python 3
#
# Date: 2012-02-16
#
#          (CC BY-NC-SA 3.0)
#===========================================================
from functools import reduce

# constants used in the multGF2 function

def setGF2(degree, irPoly):
"""Define parameters of binary finite field GF(2^m)/g(x)
- degree: extension degree of binary field
- irPoly: coefficients of irreducible polynomial g(x)
"""
if sum(irPoly) <= len(irPoly):
polyred = reduce(lambda x, y: (x << 1) + y, irPoly[1:])
else:
polyred = poly2Int(irPoly[1:])

def multGF2(p1, p2):
"""Multiply two polynomials in GF(2^m)/g(x)"""
p = 0
while p2:
if p2 & 1:
p ^= p1
p1 <<= 1
p1 ^= polyred
p2 >>= 1

#=============================================================================
#                        Auxiliary formatting functions
#=============================================================================
def int2Poly(bInt):
"""Convert a "big" integer into a "high-degree" polynomial"""
exp = 0
poly = []
while bInt:
if bInt & 1:
poly.append(exp)
exp += 1
bInt >>= 1
return poly[::-1]

def poly2Int(hdPoly):
"""Convert a "high-degree" polynomial into a "big" integer"""
bigInt = 0
for exp in hdPoly:
bigInt += 1 << exp
return bigInt

def i2P(sInt):
"""Convert a "small" integer into a "low-degree" polynomial"""
return [(sInt >> i) & 1 for i in reversed(range(sInt.bit_length()))]

def p2I(ldPoly):
"""Convert a "low-degree" polynomial into a "small" integer"""
return reduce(lambda x, y: (x << 1) + y, ldPoly)

def ldMultGF2(p1, p2):
"""Multiply two "low-degree" polynomials in GF(2^n)/g(x)"""
return multGF2(p2I(p1), p2I(p2))

def hdMultGF2(p1, p2):
"""Multiply two "high-degree" polynomials in GF(2^n)/g(x)"""
return multGF2(poly2Int(p1), poly2Int(p2))

if __name__ == "__main__":

# Define binary field GF(2^3)/x^3 + x + 1
setGF2(3, [1, 0, 1, 1])

# Alternative way to define GF(2^3)/x^3 + x + 1
setGF2(3, i2P(0b1011))

# Check if (x + 1)(x^2 + 1) == x^2
assert ldMultGF2([1, 1], [1, 0, 1]) == p2I([1, 0, 0])

# Check if (x^2 + x + 1)(x^2 + 1) == x^2 + x
assert ldMultGF2([1, 1, 1], [1, 0, 1]) == p2I([1, 1, 0])

# Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
setGF2(8, [1, 0, 0, 0, 1, 1, 0, 1, 1])

# Alternative way to define GF(2^8)/x^8 + x^4 + x^3 + x + 1
setGF2(8, i2P(0b100011011))

# Check if (x)(x^7 + x^2 + x + 1) == x^4 + x^2 + 1
assert ldMultGF2([1, 0], [1, 0, 0, 0, 0, 1, 1, 1]) == p2I([1, 0, 1, 0, 1])

# Check if (x + 1)(x^6 + x^5 + x^3 + x^2 + x) == x^7 + x^5 + x^4 + x
assert ldMultGF2([1, 1], [1, 1, 0, 1, 1, 1, 0]) == p2I([1, 0, 1, 1, 0, 0, 1, 0])

# Define binary field GF(2^571)/x^571 + x^10 + x^5 + x^2 + x
setGF2(571, [571, 10, 5, 2, 1])

# Calculate the product of two polynomials in GF(2^571)/x^571 + x^10 + x^5 + x^2 + x,
# x^518 + x^447 + x^320 + x^209 + x^119 + x + 1 and x^287 + x^145 + x^82 + + x^44
print(int2Poly(hdMultGF2([518, 447, 320, 209, 119, 1, 0], [287, 145, 82, 44])))
```

The output of the above script is:

``````[562, 529, 496, 491, 465, 406, 402, 364, 354, 291, 288, 287, 264, 253, 244,
239, 235, 201, 173, 168, 165, 164, 163, 146, 145, 102, 97, 94, 93, 83, 82,
46, 45, 44, 41, 39, 38, 37, 34, 30, 26, 23, 22]
``````

This means that the product of the polynomials $x^{518} + x^{447} + x^{320} + x^{209} + x^{119} + x + 1$ and $x^{287} + x^{145} + x^{82} + x^{44}$ is:

``````x^562 + x^529 + x^496 + x^491 + x^465 + x^406 + x^402 + x^364 + x^354 +
x^291 + x^288 + x^287 + x^264 + x^253 + x^244 + x^239 + x^236 + x^235 +
x^201 + x^173 + x^168 + x^165 + x^164 + x^163 + x^146 + x^145 + x^102 +
x^97 + x^94 + x^93 + x^83 + x^82 + x^46 + x^45 + x^44 + x^41 + x^39 +
x^38 + x^37 + x^34 + x^30 + x^26 + x^23 + x^22
``````