L7 Finite Field Arithmetics

What is a Galois (Finite) Field?

A set with a finite number of elements supporting:

• + → Addition (XOR)

• - →

• × → Multiplication (AND)

• ÷ → Inversion

Example: GF(2) is a field with two elements {0,1} → binary

What are the algebraic differences between a Group, Ring and Field?

Group: one operation with identity and inverses

Ring: addition (group) + multiplication (no inverses required)

Field: Ring where every non-zero element also has a multiplicative inverse

*Fields are an extension of Groups and related to Rings

What is a prime field GF(p)

Contains integers (0, 1, …, p-1) where p is prime

All arithmetic done mod p

Every non-zero element has a multiplicative inverse (since p is prime)

Need to learn about GF(2^m) stuff

Watch videos on this entire lecture or something

What is an irreducible polynomial?

A polynomial over GF(2) that cannot be factored into lower-degree polynomials

Acts as ‘modulus’ for extension field arithmetic - analogous to a prime number for integers

What finite field and iireducible polynomial does AES use?

GF(2^8) = GF(256)

Irreducible polynomial: P(x) = x^8 + x^4 + x³ + x + 1

Each byte (8bits) represent a polynomial in this field