Polynomial Representation
The elements of F2m are polynomials of degree less than m, with coefficients in F2; that is, {am-1xm-1 + am-2xm-2 + ... + a2x2 + a1x + a0 | ai = 0 or 1}. These elements can be written in vector form as (am-1 ... a1 a0). F2m has 2m elements.
The main operations in F2m are addition and multiplication. Some computations involve an polynomial f(x) = xm + fm-1xm-1 + fm-2xm-2 + ... + f2x2 + f1x + f0, where each fi is in F2. The polynomial f(x) must be irreducible; that is, it cannot be factored into two polynomials over F2, each of degree less than m.
Addition
(am-1 ... a1 a0) + (bm-1 ... b1 b0) = (cm-1 ... c1 c0) where each ci = ai + bi over F2. Addition is just the componentwise XOR of (am-1 ... a1 a0) and (bm-1 ... b1 b0).
Subtraction
In the field F2m, each element (am-1 ... a1 a0) is its own additive inverse, since (am-1 ... a1 a0) + (am-1 ... a1 a0) = (0 ... 0 0), the additive identity. Thus addition and subtraction are equivalent operations in F2m.
Multiplication
(am-1 ... a1 a0) (bm-1 ... b1 b0) = (rm-1 ... r1 r0) where rm-1xm-1 + ... + r1x + r0 is the remainder when the polynomial (am-1xm-1 + ... + a1x + a0) (bm-1xm-1 + ... + b1x + b0) is divided by the polynomial f(x) over F2. (Note that all polynomial coefficients are reduced modulo 2.)
Exponentiation
The exponentiation (am-1 ... a1 a0)e is performed by multiplying together e copies of (am-1 ... a1 a0).
Multiplicative Inversion
There exists at least one element g in F2m such that all non-zero elements in F2m can be expressed as a power of g. Such an element g is called a generator of F2m. The multiplicative inverse of an element a = gi is a-1 = g(-i) mod (2m-1).
Certicom is a trademark of the Certicom Corp. Copyright Certicom Corp. 1997. All rights reserved.
