Arithmetic on the Galois Field GF(2ⁿ) and GF((2ⁿ)^m).

---

WinRAR uses the EC signature algorithm to generate license. The Curve is over the Composite Field GF((2¹⁵)¹⁷).

1. GF(2) Arithmetic

The finite field with pⁿ elements is denoted GF(pⁿ) (p is a prime or a power of prime number). 

If p is a  prime number then elements in GF(p) can be represented by the numbers 0, 1, ... , (p - 1). Elements that is in GF(p) can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo p, and divisoin is multiplication by the inverse modulo p.

In particular, for a, b ∈ GF(2):

a + b = a + b (mod 2) = a XOR b;    a * b = a * b (mod 2) = a AND b.

2. GF(2ⁿ) Arithmetic

Elements of GF(pⁿ) (p is a prime or a power of prime number) can be represented as polynomials of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an irreducible polynomial of degree n over GF(p).

Thus, for elements a, b in GF(pⁿ) can be represented by the polynomials:

a = λ_n-1 x^n-1 + λ_n-2 x^n-2 + ... + λ₁ x + λ₀ (λ_i ∈ GF(p)),

b = μ_n-1 x^n-1 + μ_n-2 x^n-2 + ... + μ₁ x + μ₀ (μ_i ∈ GF(p)).

And,

a + b = (λ_n-1 + μ_n-1) x^n-1 + ... + (λ₀ + μ₀),

a - b = (λ_n-1 - μ_n-1) x^n-1 + ... + (λ_{0 ^-} μ₀),

a x b = (λ_n-1 x^n-1 + λ_n-2 x^n-2 + ... + λ₁ x + λ₀)(μ_n-1 x^n-1 + μ_n-2 x^n-2 + ... + μ₁ x + μ₀) mod R,

a / b = a x (b^-1), b^-1 is satisfied that b x (b^-1 ) = 1.

It is conventional to express elements of GF(2ⁿ) and the irreducible polynomial as n and n+1 bit numbers, with the coefficient of each term in a polynomial represented by one bit in the corresponding element's binary expression.

For example:

a = x⁶ + x⁴ + x + 1 ∈ GF(2⁸) Can be expressed as 0b01010011 or 0x53.

Irreducible polynomial R = x⁸ + x⁴ + x³ + x + 1 Can be expressed as 0b100011011 or 0x11B.

So, for a, b ∈ GF(2ⁿ):

a + b = a - b = a BITXOR b.

And a x b can be computed by this python programme:

def mul(a, b, n, ir_poly):
"""
Input: a, b in GF(2^n). And irreducible polynomial ir_poly.
Output: a x b
"""
    mask = 2**n - 1
    res = 0
    while ((a != 0) and (b != 0)):
        if b & 1:
            res ^= a
        if a & (1<<(n-1)):
            a = (a << 1) ^ ir_poly
        else:
            a <<= 1
        b >>= 1
    res = res & mask
    return res

To compute b^-1, you need to create the exponent table (exp_tab) and logarithm table (log_tab). You can use this python programme:

def table(n, ir_poly):
"""
Input: GF(2^n). And irreducible polynomial ir_poly.
Output: exp_tab, log_tab
"""
    exp_tab = []
    log_tab = [0]*(2 ** n)
    generator = 0
    while len(set(exp_tab)) != ((2 ** n) - 1):
        exp_tab.clear()
        exp_tab.append(1)
        generator += 1
        for i in range(1, 2 ** n):
            exp_tab.append(mul(exp_tab[i-1], generator, n, ir_poly))
    for i in range(0, 2 ** n):
        log_tab[exp_tab[i]] = i
    return exp_tab, log_tab

Then b^-1 ≠ 0 ∈ GF(2ⁿ), can be computed with this python programme:

def inv(a, n, exp_tab, log_tab):
"""
Input: a in GF(2^n), exp_tab, log_tab
Output: a^(-1)
"""
    if a >= (2 ** n):
        raise Exception("not in this Galois Field")
    if a == 0:
        raise Exception("div zero")
    return exp_tab[ (((2 ** n) -1) - log_tab[a]) % ((2 ** n) -1)]

3. GF((2ⁿ)^m) Arithmetic

GF((2ⁿ)^m) is the special kind of GF(p^m) (p = 2ⁿ). So elements in GF((2ⁿ)^m) can be represented as polynomials of degree strictly less than m over GF(2ⁿ). And the four arithmetic operations in GF(2ⁿ) have been described in the section 2.

An element a in GF((2ⁿ)^m) can be expressed as an array {a_0, a_1, ... , a_(m - 1)}, and a_i ∈ GF(2ⁿ).

The irreducible polynomial can be expressed as an array {a_0, a_1, ... , a_m}, and a_i ∈ GF(2ⁿ).

So + and - over GF((2ⁿ)^m) can be computed by this python programme:

def add(a, b):
    """
    GF2_n_add is a function that computers + over GF(2^n) 
    """
    return [GF2_n_add(i[0],i[1]) for i in zip(a, b)]
def sub(a, b):
    """
    GF2_n_sub is a function that computers - over GF(2^n) 
    """
    return [GF2_n_sub(i[0],i[1]) for i in zip(a, b)]

And multiplication over GF((2ⁿ)^m) can be computed by this python programme:

def mul(a, b, m, ir_poly):
    """
    GF2_n_add is a function that computers + over GF(2^n) 
    GF2_n_sub is a function that computers - over GF(2^n) 
    GF2_n_mul is a function that computers x over GF(2^n) 
    GF2_n_div is a function that computers / over GF(2^n) 
    """
    if len(a) != m:
        raise Exception("a is not in this Galois Field")
    if len(b) != m:
        raise Exception("b is not in this Galois Field")
    if set(a) == {0}:
        return [0]*m
    if set(b) == {0}:
        return [0]*m
    _a = a.copy()
    _b = b.copy()
    res = [0]*(2*m)
    for i in range(0,m):
        for j in range(0,m):
            temp1 = GF2_n_mul(_a[i], _b[j])
            res[i + j] = GF2_n_add(res[i + j], temp1)

    for i in range(2*m-1,m-1,-1):
        if res[i] != 0:
            for j in range(0,m + 1):
                res[i - m + j] = GF2_n_sub(res[i - m + j], GF2_n_mul(res[i], GF2_n_div(ir_poly[j], ir_poly[m])))

    return res[:m]

The divisoin over GF((2ⁿ)^m) can be computed by this python programme, use Itoh–Tsujii inversion algorithm:

def GF_inv(a, m, n, ir_poly):
    """
    GF2_n_add is a function that computers + over GF(2^n) 
    GF2_n_sub is a function that computers - over GF(2^n) 
    GF2_n_mul is a function that computers x over GF(2^n) 
    GF2_n_div is a function that computers / over GF(2^n) 
    """
    if set(a) == {0}:
        raise Exception("div zero")
    else:
        base = a.copy()
        for r in range(0,m-1): 
            for rr in range(0,n):
                base = mul(base, base, m, ir_poly)
            ans = mul(ans, base, m, ir_poly)
        temp = mul(ans, a, m, ir_poly)
        temp[0] = GF2_n_div(0x1, temp[0])
        ans = mul(ans, temp, m, ir_poly)
        return ans