lpetrich
Contributor
I find the theory of finite fields very elegant.
The simplest of them are Z(p), where p is a prime number.
The rest are constructed as polynomials sum over k from 0 to n-1 of ak*xk of a variable x, where the ak are in Z(p).
The variable x is interpreted as satisfying a nth-degree monic polynomial P(x) with coefficients in Z(p). When one multiples two elements, one divides out P(x) and uses the remainder. P(x) should be a "irreducible polynomial", one that cannot be factored.
Monic polynomial: its highest-degree coefficient is 1. If it is some other value, then one can multiply the polynomial by that value's multiplicative inverse to make the polynomial monic. Unlike the situation with rational-number coefficients.
Finite fields are often called GF(p^n) ("Galois Field"). GF(p) = Z(p). Every field GF(p^n) has subfields GF(p^m) where m evenly divides n.
To within isomorphisms, there is only one field with order p^n. That means that one can choose whatever primitive polynomial one wants for P(x) above.
The field's addition group is Z(p)^n, while its multiplication group is Z(p^n-1).
The number of irreducible polynomials in GF(p^n) is
(1/n) * sum over m that evenly divides n of μ(m) * pn/m
μ is the Moebius mu function:
If n contains a square of a prime, 0
Otherwise, (-1)^(number of prime factors of n)
Also, μ = sum over k where gcd(k,n) = 1 of exp(2*pi*i*k/n) -- the primitive nth roots of unity
-
Some examples:
GF(p) -- irreducible polynomials x + k (0 <= k < p)
GF(4): 0, 1, x, x+1 -- irreducible polynomial x2 + x + 1
GF(8): 0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 -- irreducible polynomials x3+x+1, x3+x2+1
GF(9): 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2 -- irreducible polynomials x2+1, x2+x+2, x2+2x+2
-
Do any of you know of any properties of fields GF(2^n) that make them especially suited for computer implementation?
The simplest of them are Z(p), where p is a prime number.
The rest are constructed as polynomials sum over k from 0 to n-1 of ak*xk of a variable x, where the ak are in Z(p).
The variable x is interpreted as satisfying a nth-degree monic polynomial P(x) with coefficients in Z(p). When one multiples two elements, one divides out P(x) and uses the remainder. P(x) should be a "irreducible polynomial", one that cannot be factored.
Monic polynomial: its highest-degree coefficient is 1. If it is some other value, then one can multiply the polynomial by that value's multiplicative inverse to make the polynomial monic. Unlike the situation with rational-number coefficients.
Finite fields are often called GF(p^n) ("Galois Field"). GF(p) = Z(p). Every field GF(p^n) has subfields GF(p^m) where m evenly divides n.
To within isomorphisms, there is only one field with order p^n. That means that one can choose whatever primitive polynomial one wants for P(x) above.
The field's addition group is Z(p)^n, while its multiplication group is Z(p^n-1).
The number of irreducible polynomials in GF(p^n) is
(1/n) * sum over m that evenly divides n of μ(m) * pn/m
μ is the Moebius mu function:
If n contains a square of a prime, 0
Otherwise, (-1)^(number of prime factors of n)
Also, μ = sum over k where gcd(k,n) = 1 of exp(2*pi*i*k/n) -- the primitive nth roots of unity
-
Some examples:
GF(p) -- irreducible polynomials x + k (0 <= k < p)
GF(4): 0, 1, x, x+1 -- irreducible polynomial x2 + x + 1
GF(8): 0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 -- irreducible polynomials x3+x+1, x3+x2+1
GF(9): 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2 -- irreducible polynomials x2+1, x2+x+2, x2+2x+2
-
Do any of you know of any properties of fields GF(2^n) that make them especially suited for computer implementation?