Maths and Computing:

Galois Field Arithmetic: Entry

---

---

Calculation in GF(16)

x:

y:

---

Workings

---

Workings

---

Addition and subtraction use the binary XOR (Exclusive OR) operation

XOR Operation

0 + 0 = 0 XOR 0 = 0

0 + 1 = 0 XOR 1 = 1

1 + 0 = 1 XOR 0 = 1

1 + 1 = 1 XOR 1 = 0

Example for the elements 14 and 5 from GF(16)

1 1 1 0 14 0 1 0 1 5 XOR 1 0 1 1 11

x3  + x2  + x 14    x2  + 1 5 XOR    x3  + x  + 1 11

---

Table of Values

Addition and Subtraction between elements in GF(16)

+	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	0	3	2	5	4	7	6	9	8	11	10	13	12	15	14
2	2	3	0	1	6	7	4	5	10	11	8	9	14	15	12	13
3	3	2	1	0	7	6	5	4	11	10	9	8	15	14	13	12
4	4	5	6	7	0	1	2	3	12	13	14	15	8	9	10	11
5	5	4	7	6	1	0	3	2	13	12	15	14	9	8	11	10
6	6	7	4	5	2	3	0	1	14	15	12	13	10	11	8	9
7	7	6	5	4	3	2	1	0	15	14	13	12	11	10	9	8
8	8	9	10	11	12	13	14	15	0	1	2	3	4	5	6	7
9	9	8	11	10	13	12	15	14	1	0	3	2	5	4	7	6
10	10	11	8	9	14	15	12	13	2	3	0	1	6	7	4	5
11	11	10	9	8	15	14	13	12	3	2	1	0	7	6	5	4
12	12	13	14	15	8	9	10	11	4	5	6	7	0	1	2	3
13	13	12	15	14	9	8	11	10	5	4	7	6	1	0	3	2
14	14	15	12	13	10	11	8	9	6	7	4	5	2	3	0	1
15	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0

---

Multiplication use the binary AND and XOR operations

AND Operation

0 × 0 = 0 AND 0 = 0

0 × 1 = 0 AND 1 = 0

1 × 0 = 1 AND 0 = 0

1 × 1 = 1 AND 1 = 1

It does a long multiplication using the binary values or a polynomial using the equaivalent polynomials expressions

Any add operation uses the XOR operation

Finally the result of the multiplication is divided by the selected irreducible polynomial to give a remainder

The remainder is the final result of the multiplication

Alternatively the multiplication table below can be used

Example for the elements 14 and 5 from GF(16) using the irreducible polynomial 0 and the table below.

1 1 1 0 14 0 1 0 1 5 × 0 1 1 0 54

x3  + x2  + x 14    x2  + 1 5 ×    x2  + x 54

For full workings, perform the operation in the calculation tab

---

Tables of Values for Multiplication

Irrecucible Polynmial = 0

×	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	2	4	6	8	10	12	14	16	18	20	22	24	26	28	30
3	3	6	5	12	15	10	9	24	27	30	29	20	23	18	17
4	4	8	12	16	20	24	28	32	36	40	44	48	52	56	60
5	5	10	15	20	17	30	27	40	45	34	39	60	57	54	51
6	6	12	10	24	30	20	18	48	54	60	58	40	46	36	34
7	7	14	9	28	27	18	21	56	63	54	49	36	35	42	45
8	8	16	24	32	40	48	56	64	72	80	88	96	104	112	120
9	9	18	27	36	45	54	63	72	65	90	83	108	101	126	119
10	10	20	30	40	34	60	54	80	90	68	78	120	114	108	102
11	11	22	29	44	39	58	49	88	83	78	69	116	127	98	105
12	12	24	20	48	60	40	36	96	108	120	116	80	92	72	68
13	13	26	23	52	57	46	35	104	101	114	127	92	81	70	75
14	14	28	18	56	54	36	42	112	126	108	98	72	70	84	90
15	15	30	17	60	51	34	45	120	119	102	105	68	75	90	85

---

Division

Division is done by multiplying by the inverse of the divisor

---

Tables of Inverse Values

Irrecucible Polynmial = 0

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Groups

A group consists of a non-empty set G and an operation *

Closure: If a ∈ G and b ∈ G then a * b ∈ G

Group Axioms

Associativity: For all a, b and c in G, (a * b) * c = a * (b * c)

Identity element: There exists e ∈ G such that for every a ∈ G, a * e = e

Inverse element: There exists b ∈ G such that for every a ∈ G, a * b = e

---

Group G: GF(16) under Addition

Let A, B and C be elements in the set G

Set

The set of 4-bit binary values

The polynomials of order 4 with coefficients of 0 or 1

Operation

XOR (Exclusive OR)

The application of a bitwise XOR between the corresponding bits of two elements expressed as a binary value

The application of the XOR operation to the corresponding coefficients of two elements expressed as polynomials

0 XOR 0 = 1, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0

Closure

A bitwise XOR between two 4-bit values results in an 4-bit value

A bitwise XOR between the coefficients of two polynomials of order 4 results in a polynomial of order 4

A XOR B a ∈ G

Associativity

The XOR operation is associative

(A XOR B) XOR C = A XOR (B XOR C)

Identity Element

A XOR 0 = A

The identity element is 0 for all elements in G

Inverse Element

A XOR A = 0 (The inverse element)

For each element in G, the inverse element is itself

Groups

A group consists of a non-empty set G and an operation ◦

Closure: If a ∈ G and b ∈ G then a ◦ b ∈ G

Group Axioms

Associativity: For all a, b and c in G, (a ◦ b) ◦ c = a ◦ (b ◦ c)

Identity element: There exists e ∈ G such that for every a ∈ G, a ◦ e = e

Inverse element: There exists b ∈ G such that for every a ∈ G, a ◦ b = e

---

Group G: GF(16) under Multiplication with the Primative Polynomial 0

Let A, B and C be elements in the set G

Set

The set of 4-bit binary values

The polynomials of order 4 with coefficients of 0 or 1

Operation

Polynomial multiplication performing addition with the XOR operation and then dividing by 0 using the XOR operaition for subtractions

Closure

Dividing any polynomial by a polynomial of order 4+1 results in a polynomial order 4 or less

Associativity

f(x)g(x) = q(x)p(x) + r(x)

f(x)g(x) = q(x)p(x) + r(x)

Identity Element

A ◦ 1 = A

The identity element is 1 for all elements in G

Inverse Element

A XOR A = 0 (The inverse element)

For each element in G, the inverse element is itself

Irrecucible Polynmial = 0

Inverse Values

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

---

---

Irreducible Polynomials

Polynomial	Binary Value	Primitive	n
x4 + x + 1	10011	Yes	n = 15
x4 + x3 + 1	11001	Yes	n = 15
x4 + x3 + x2 + x + 1	11111	No	n = 5

---

Reducible Polynomials

Polynomial	Binary Value	Factors
x4 + 1	10001	(x + 1)(x3 + x2 + x + 1) (x2 + 1)2
x4 + x	10010	(x)(x3 + 1) (x + 1)(x3 + x2 + x) (x2 + x)(x2 + x + 1)
x4 + x2	10100	(x)(x3 + x) (x + 1)(x3 + x2) (x2)(x2 + 1) (x2 + x)2
x4 + x2 + 1	10101	(x2 + x + 1)2
x4 + x2 + x	10110	(x)(x3 + x + 1)
x4 + x2 + x + 1	10111	(x + 1)(x3 + x2 + 1)
x4 + x3	11000	(x)(x3 + x2) (x2)(x2 + x)
x4 + x3 + x	11010	(x)(x3 + x2 + 1)
x4 + x3 + x + 1	11011	(x + 1)(x3 + 1) (x2 + 1)(x2 + x + 1)
x4 + x3 + x2	11100	(x)(x3 + x2 + x) (x2)(x2 + x + 1)
x4 + x3 + x2 + 1	11101	(x + 1)(x3 + x + 1)
x4 + x3 + x2 + x	11110	(x)(x3 + x2 + x + 1) (x + 1)(x3 + x) (x2 + 1)(x2 + x)

---

Select a polynomial to see details relating to whether it is primitive