Chapter 2  Introduction to Algebra
Groups
Group: a binary operation denoted as * on a set that meets these conditions:
 a * (b*c) = (a*b) * c (associative)
 a*element = element*a = a (has an identity element)
 element_1*element_2 = identity (each member has a pair member that when applied makes the identity element)
Example of a group: XOR on binary numbers (Group = {0,1}, binary operation = XOR, identity elem = 0). Denoted
as ⊕. Also called modulo2 addition.
 Order: the size of the group (e.g. order of binary numbers group is 2)
 finite group: has a fixed, known amount of elements (not infinite)
Fields
Have two elements: addition and multiplication, which meet the following:
 commutative when using +
 Has a zero element for + where a+0=a
 Multiplication with nonzeros is commutative, has a unit element for * where a*1=a
 * is distributive with +: a*(b+c) = a*b + a*c
Like with groups, Order is the size of the field and a finite field
has a finite, known number of elements
Prime Fields
 Denoted GF(p) where p is a prime number
 Addition and multiplication are defined as modulop
addition and multiplication
 E.g. GF(2) uses mod 2 multiplication and mod 2 addition
 Example: GF(7)
 G = {0,1,2,3,4,5,6}
 3 / 2 = 5
 3 / 2 = 3 * (2^{1}) = 3 * 4 = 5
 2^{1} = 4 because (2*4) % 7 = 1 (multiplicative inverse)
 3 * 4 = 5 because (3*4) % 7 = 5
 3  6 = 4
 3  6 = 3 + (6) = 3 + 1 = 4
 6 = 1 because (6+1) % 7 = 0 (additive inverse)
 Characteristic (λ): the number of increments it takes for the field to
loop back to 0. in GF(p) this is always equal to p
 e.g. λ of GF(7) = 7 because (1+1+1+1+1+1+1) % 7 = 0
Binary Field Arithmetic
Most error coding algs use GF(2) or GF(2^{m})
 Uses Modulo 2 addition and multiplication
 Example: solve the set of equations (just like regular algebra)
 1) X + Y = 1
 2) X + Z = 0
 3) X + Y + Z = 1

 (X+Y)+Z=1
 1+Z=1 > Z=0 (substitute X+Y in eq 3 with eq 1)
 X+0=0 > X=0 (substitute Z in eq 2 with 0)
 0+Y+0=1 > Y=1 (substitute X and Z in eq 3 with 0)
 X=0, Y=1, Z=0
Binary Field Polynomials
Regular polynomials where there is one variable and
its coefficients are either 0 or 1
 Like so: f(X) = f_{0} + f_{1}X + f_{2}X^{2} + f_{3}X^{3} ...
 where f_{0}, f_{1}, ... are 0 or 1
 "A polynomial over GF(2)" means a polynomial with coefficients as 0 or 1
Binary Polynomial Arithmetic
 Addition/subtraction
 f(X) + g(X) = ((f_{0}+g_{0})%2) + ((f_{1}+g_{1})%2)X + ((f_{2}+g_{2})%2)X^{2} ...
 Multiplication
 f(X) * g(X) = f_{0}*g_{0} + (f_{0}*g_{1} + f_{1}*g_{0})X + (f_{0}*g_{2} + f_{1}*g_{1} + f_{2}*g_{0})X^{2} ...
 Where all addition/multiplication is done Modulo 2
 Division  Euclid's division algorithm
 given g(X) is NOT 0, f(X)/g(X) = q(X)g(X)+r(X), where q(X) is the quotient and r(X) is the remainder
 Example: f(X) = 1 + X + X^{4} + X^{5} + X^{6}, g(X) = 1 + X + X^{3}
Properties of Binary Field Polynomials
 If a is a root of f(X) (f(a)=0), then f(X) is divisible by Xa
 If the polynomial has an even number of terms, it is divisible by X+1
 Irreducible: for f(X) of degree m, f(X) is irreducible if it isn't divisible
by any g(X) of degree less than m and greater than 0.
 Any irreducible f(X) of degree m evenly divides X^{2m1} + 1
 Primitive: an irreducible f(X) is primitive if X^{2m1}+1 is the
smallest polynomial it divides evenly
 f(X)^{2i} = f(X^{2i}) for i >= 0
Galois Field GF(2^{m})
Field over GF(2) with 2^{m} elements as opposed to just 0 and 1
 Field F = {0,1,a,a^{2},a^{3},...}
with 2^{m} elements (F finite = {0,1,a,a^{1},
...a^{2m2}})
 Addition, subtraction, multiplication done Modulo 2  Notably, when using a:
 a^{i} * a^{j} = a^{i+j}
 a^{0} = 1
 a^{i} + a^{j} = (a_{i,0} + a_{j,0}) +
(a_{i,1} + a_{j,1})a +
... (a_{i,m1} + a_{j,m1})
a^{m1} (using modulo 2 addition)
 0<= i < 2^{m}1
 a_{i}(X) = a_{i,0} + ... a_{i,m1}X^{m1}
is the remainder from dividing X^{i} by p(X)

p(X) is primitive with degree m over GF(2), where p(a) = 0
(a is a root of p(X))
 a^{2m1} = 1 using modulo 2 addition
 Similarly, a^{2m+i}
loops back around starting at a^{0}=1
 e.g. a^{16}=a, a^{17}=a^{2},
a^{18}=a^{3}, etc.
 Example using a within F finite (also denoted F^{*})
 m=4, p(X) = 1+X+X^{4}
 Since a must be a root of p(X),
p(a)=1+a+a^{4} = 0
 1+a = a^{4} (using mod 2 arith (1 = 1))
 Use this identity to form the rest of F^{*}
 a^{5}=a*a^{4}=a(1+a)=a+a^{2}
 a^{6}=a*a*a^{4}=a^{2}*(1+a)=a^{2}+a^{3}
 ...
 a^{15} = 1 (last property above (2^{4}1 = 15))
 So F^{*} = {0,1,a,a^{2},a^{3},a^{4},
(a+a^{2}),(a^{2}+a^{3}),...}
 The a^{i} representation makes multiplication easier
 a^{5}*a^{7}=a^{12}
 a^{12}*a^{7}=a^{19}=
a^{15}*a^{4}=1*a^{4}=a^{4}
 The polynomial representation makes addition easier
 a^{5}+a^{7}=(a+a^{2})+(1+a+a^{3})=1+(1+1)a+a^{2}+a^{3}
=1+a^{2}+a^{3}=a^{13}
 Binary representation makes addition yet again even easier
 Each bit represents a coefficient in the polynomial, e.g. (1011)
= 1+a^{2}+a^{3}
 Given A=1+a^{2}+a^{3}=(1011), B=1+a^{2}=(1010),
 A+B = (a_{0}+b_{0})(a_{1}+b_{1})...
(a_{3}+b_{3})
 =(1+1)(0+0)(1+1)(1+0)=(0001)=a^{3}
 Can be done as a single XOR in C: A^B = (1011)^(1010)=0001
Properties of GF(2^{m})
 A polynomial without real roots in GF(2) can have roots in GF(2^{m})
 Ex: X^{4}+X^{3}+1 has no roots in GF(2)
 Plugging in elements from the example GF(2^{4})
 f(X)=X^{4}+X^{3}+1, X=a^{7}
 (a^{7})^{4}+(a^{7})^{3}+1
 a^{28}+a^{21}+1
 a^{13}+a^{6}+1
 (1+a^{2}+a^{3})+(a^{2}+a^{3}) + 1
 (1101) + (1100) + 1 = (0001) + 1 = 0
 Hence a^{7} is a root of f(X). The same can be found for
a^{11},a^{13}, and a^{14}
 Conjugate of a polynomial root
 If B is a polynomial in GF(2^{m}) and is a root
of a polynomial f(X) in GF(2), then B^{2l}
is also a root of f(X) for any l >=0
 B^{2l} is a conjugate of B
 Minimal polynomial of B
 ϕ(X) is the polynomial of the smallest degree where B
is a root (ϕ(B)=0), ϕ(X) is in GF(2)
and B is in GF(2^{m})
 Example: the minimum polynomial ϕ(X) for B=0 is
ϕ(X)=X (since ϕ(B)=0)
 Example: ϕ(X) for B=1 is
ϕ(X)=1+X (since ϕ(B)=1+1=0)
Finding the Minimal Polynomial of B
 ϕ(X) = (X+B^{20}) *
(X+B^{21}) * ...
(X+B^{2e1})
 Where e is the smallest number so that
B^{2e}=B
 Example: B=a^{3} in GF(2^{4})
 B^{2}=(a^{3})^{2}=a^{6}
 B^{4}=(a^{3})^{4}=a^{12}
 B^{8}=(a^{3})^{8}=a^{24}=a^{9}
 ϕ(X) = (X+a^{3}) *
(X+a^{6}) *
(X+a^{12}) *
(X+a^{24})
 which simplifies to ϕ(X) = X^{4} + X^{3} + X^{2} + X + 1
Example Computations Using GF(2^{m})
 Solve the linear equations
X+a^{7}Y = a^{2} and
a^{12}X + a^{8}Y = a^{4}
over GF(2^{4})

 We can also use Cramer's rule to solve the set of equations (see section 2.6)
 Find the roots of the equation f(X) = X^{3} + a^{7}X + a
 Can't use quadratic equation because of the divide by 2, and in GF(2), 2=(1+1)=0

Instead, plug in and try all of the power representations a^{i}
for X and see which ones are roots (f(X) = 0)
 f(a^{6}) = (a^{6})^{2} + (a^{7})(a^{6}) +
a = a^{12} + a^{13} + a = 0
 f(a^{10}) = (a^{10})^{2} + (a^{7})(a^{10}) +
a = a^{5} + a^{2} + a = 0
 The above two previous examples are used in BCH and ReedSolomon coding
Vector Spaces
Vector space over GF(2)
 ntuple over GF(2): (a_{0},a_{1},a_{2},a_{3}...a_{n1})
where a_{0}...a_{n1} are in GF(2) (equal 0 or 1)
 V_{n} = the set of all possible ntuples (2^{n} possible tuples)
 for ntuples u and v,
 u + v = (u_{0} + v_{0}, u_{1} + v_{1}, ...)
 Where addition is Modulo 2
 v+v=0 (since 1+1=0)
 The additive inverse of v (v) is v itself
 Scalar multiplication: a*v = (a*v_{0},a*v_{1},...)
 Multiplication is Modulo 2
 Linear combination: a_{1}v_{1} + a_{2}v_{2} + ... a_{k}v_{k}
a_{1...k} and v_{1...k} are k scalars and vectors from vector space V and field F
Matrices
A k by n matrix G over GF(2) has k rows and n columns, where
each entry is in GF(2) (0 or 1)
 Matrix can also be represented by its k rows, where each row is a ntuple vector
 Row space: If the k rows (assuming k <= n) are linearly independant, then any linear
combination of these rows called the row space of G
 Elementary row operations:
Adding or swapping any of these rows is valid and is called a elementary row operation
 Adding matrices:
 The number of rows and cols must be the same
 Uses scalar addition: A+B=C, where C_{i,j} = A_{i,j}+B_{i,j}
 Multiplying matrices:
 Number of cols in A must equal the number of rows in B
 Each entry in result is the dot product/inner product of the row in A and col in B