20191105
Contents
// 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] /
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
|
|
Can trial divide up to sqrt(n) too!
|
|
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