// Chapter 5

-> Finite Field Theorem

Z_p is a field iff p is prime

|F| = 9

|F| = p^n

Alpha powers -> Expressing higher powers in terms of lower alpha powers up to p

Can represent higher alpha powers as factors of lower alphas

inverse powers can be used

Show that m = x^2 + 1 is irreducible over Z_3 and construct GF(9)

9 is 3^2, so dealing with numbers mod 3, need two copies

So need, constants and up to degree one terms

To get the multiplicative structure, we also need degree two terms

Since m(0) =/= 0, and m(1) = m(2) = 2 =/= 0, m has no roots in Z_3

GF(9) ~= Z_3[x] / = Z_3[x] = {ax + b : a,b in Z_3}

Try find a primitive element alpha = x -> alpha^2 + 1 =0, a^2 = -1 = 2 then a^0 = 1, a^1 = a, a^2= 2, a^3 = 2a, a4 = 2a^2 = 4 = 1 nope (1 reached at a4 instead of a8)

try g = a + 1 = x+1

g0 = 1 g1 = a+1 g2 = 2a g3 = 2a+1 g4 = 2 g5 = 2a+2 g6 = a g7 = a+2 g8 = 1

g = a+1 is primitive, so generates GF(9)

Every finite field F=GF(q) has a primitive element if Beta is a primitive element of F, then B^k is also a primitive element of F iff gcd(k,q-1) = 1 F has phi(q-1) primitive elements

is F is a finite field with p^n elements, then a^p^n = a for all a in F

Each element beta in GF(p^n) is a root of x^p^n - x

The minimal polynomial of an element B of a finite field GF(p^n) is the monic polynomial m in Z_p[x] with the smallest degree, and m(B) = 0

if f is irreducible and f(B) = 0 then f is the minimal polynomial of B

(a+b)^p = a^p + b^p in Z_p

If B is a root of G in Z_p[x] hen so is B^p^i for all i

Each element B in GF(p^n) has minimal polynomial

g(x) = PRODUCTTHING(x- B^p^i)

where the powers of B^p^i are distinct

Minimal polynomial of a^5

Find the powers (a^5)^2i

a^5, a^10, a^20=a^5

So a^5, a^10

Hence minimal polynomial (x-a^5)(x-a^10)

///////////////////////

Primality Testing

Trial division

1
2
3
4

for i = 2 to n-1:
  if n % i == 0:
    return false
return true;

Can trial divide up to sqrt(n) too!

1
2
3
4

for i = 2 to sqrt(n):
  if n % i == 0
    return false
return true

Psuedo-prime test

If n is composite - then false (but, duh).

Let $a$ be any number if gcd(a,n) =/= 1 then false if $a^{n-1} =/= 1 (mod n)$ then false

Recall Fermat’s Little Theorem: a^n-1 = == 1 mod n if gcd(a,n) = 1 for n prime.

• Lucas’ test
• Miller-Rabin test
• AKS test