Transcript Small Finite Fields

Small Finite Fields
computation
Abstract: This note describes how to
use the GF(p^{n}).xls worksheet to
compute Small Finite Fields.
© César Bravo, 2009.
Interface
Input Data

To compute the Finite Field GF(pn),
the user must provide:
• A prime number p at cell C1
• An integer n at cell C2

OBS: No consistency check is made
on p, since a Finite Field’s user must
be well aware that there is no Finite
Field GF(pn) when p is NOT prime.
“GF(p)” button



It computes the addition and
multiplication tables of the base field
GF(p) as the usual “mod p”
operations on the ring Zp.
The addition table is stored on the
“(GL(p), + )” plan.
The multiplication table is stored on
the “(GL(p), x )” plan.
Example: (GL(2), + )


This is the usual Cayley table notation for
additive groups.
The grid was added for readability: the
routines does not provide any grid.
Example: (GL(2), x )


This is the usual Cayley table notation for
multiplicative groups.
The grid was added for readability: the
routines does not provide any grid.
“GF(p)[x] polynomials” button



The polynomials able to be checked for
irreducibility are computed by this button
The polynomials are stored on the “p^{n}
Able Monic Polynomials” plan.
Each row stores a polynomial:
•
•
•
•
represented by its coefficients,
With a name computed over its coefficients,
evaluated over each GF(p) element,
With a flag for irreducibility.
Example: 2^{5} polynomials
Cell I5=0 tell us that 1 is a root
of p_{39}: p_{39}(1)=0.
So p_{39} is not irreducible and
this is indicated storing 0 in the
cell K5

Row 8 stands for
In the case of p_{61} the cells
H16=1 and I16=1 shown that
p_{61} is irreducible and this is
indicated storing 1 in the cell
K16
• 1.x5 + 0.x4 + 1.x3 + 1.x2 + 0.x + 1

Row 8 name, p_{45}, is computed as:
• 1.25 + 0.24 + 1.23 + 1.22 + 0.2 + 1 = 32 + 8 + 4 + 1 = 45
“Irreducible polynomials” button


Simply deletes, on the “p^{n} Able
Monic Polynomials” plan, each row
with the irreducibility flag settled to
zero.
After that, the plan is renamed to
“p^{n} Irreducible polynomials”
Example: 2^{5} Irreducible polynomials
“p(x) root powers” button



Computes the powers of the root of
the first irreducible polynomial as
linear combinations of the basis:
{rn-1, rn-2, …, r1=r, r0=1}.
The results are stored on the
“p_{name} root powers” plan
The first column is the logarithm of
the root’s power
Example: p_{35} root powers
“p-adic expansion” button


Regards each linear combination
representing a root power on
“p_{name} root powers” plan as a padic expansion and convert it to a
decimal number.
The results are stored on column “padic expansion”
Example: p-adic p_{35} root powers
since 21st power is 1
then, the roots of the
p_{35} polynomial are not
primitive and so, they do
not generate GF(25).
“Roots order” button

Computes, for each irreducible
polynomial:
• Its root powers
• The corresponding p-adic expansion

And, store in column “Root order” of
“p^{n} Irreducible Polynomials” plan
the logarithm of the power yielding
1.
Example: 2^{5} Irreducible polynomials roots order
Cells M2=21 and M6=21 indicates that the
polynomials p_{35} and p_{49} has not primitive
roots, since their root's order is 21, not being able
to generate the 25 = 32 elements of GF(25).
“Primitive roots” button


Simply deletes, from “p^{n}
Irreducible Polynomials” plan, any
polynomial whose root order is
different from pn.
The plan is then renamed to “p^{n}
Generator Polynomials”
Example: Primitive roots
All these six polynomials have primitive roots and
so, any of them can be used to calculate the
addition/multiplication tables of GF(25).
“(GF(p^{n}), +)” button




Computes the addition table of GF(pn), using the
linear combinations from the “p-adic p_{name}
root powers” plan to add (mod p) the root powers
on that plan.
The result is stored on the “p_{name}
(GF(p^{n}), +)” plan but is NOT in Cayley table
notation; the prefix indicates that this table was
computed using the polynomial p_{name}
On the right of each row index are stored its padic coefficients
Below each column index are stored its p-adic
coefficients
Example: (GF(2^{5}), +)
“(GF(p^{n}), x)” button




Computes the multiplication table of GF(pn),
using the logarithms from the “p-adic p_{name}
root powers” plan to multiply (mod pn) the root
powers on that plan.
The result is stored on “p_{name} (GF(p^{n}),
x)” plan but is NOT in Cayley table notation; the
prefix indicates that this table was computed
using the polynomial p_{name}
On the right of each row index is stored its
logarithm
Below each column index is stored its logarithm
Example: p_{37} (GF(2^{5}), x)
Computed parameters



The "GF(p)[x] polynomials" button
stores the quantity of able monic
polynomials on the C8 cell of Plan1
The “Irreducible polynomials" button
stores this quantity on the C16 cell of
Plan1
The “Primitive roots" button stores
the quantity of primitive roots on the
C25 cell of Plan1
Example: Computed parameters
There are 16 viable monic polynomials
Of them, only 8 are irreducible
And of those 8, only 6 have primitive roots
Which polynomial is used?




After “p(x) root powers” + “p-adic expansion”:
the first.
After “Primitive roots” : the last.
If both have primitive roots you are done.
Otherwise, to assure that the first (remaining)
polynomial on the list has primitive roots:
• execute “Primitive roots”,
• execute “p(x) root powers”,
• execute “p-adic expansion”.

After that, the tables will be computed using the
first irreducible polynomial with primitive roots.
Using another polynomial



Execute “Primitive roots”.
Put the chosen polynomial on the top
of the list.
Execute
• “p(x) root powers” + “p-adic expansion”

Compute the tables
Example: Promoting p_{59} polynomial


The polynomial p_{45} was promoted to the top
Now, the tables must be recomputed, executing:
• (GF(p^{n}), + ) button
• (GF(p^{n}), x ) button
Example: p_{59} (GF(2^{5}), +)
Yes, this is the same as p_{37} (GF(2^{5}), +). Why?
Example: p_{59} (GF(2^{5}), x)
Compare with p_{37} (GF(2^{5}), x). Look here.
Implementation remarks



The algorithms implementations are
straightforward and must allow the reader
to retargeted them to another
programming language after some minor
modifications.
Use of synthetic division can speed-up
computation of irreducible polynomials
(not implemented).
Identification of primitive root can be
speeded-up discarding additional power
computation after a non-primitive root
was identified (not implemented).
Galois Fields web texts

Leviathan. Galois Theory for Dummies – Part I. url:
http://yaniv.leviathanonline.com/blog/math/galois-theory-fordummies-part-i/

Baker. An introduction to Galois Theory. url:
http://www.maths.gla.ac.uk/~ajb/dvi-ps/Galois.pdf

Milne. Fields and Galois Theory. url:
http://www.jmilne.org/math/CourseNotes/ft.html


Cherowitzo. Combinatorial Structures Lecture Notes, Math 6406
spring 2006. url:
http://math.ucdenver.edu/~wcherowi/courses/m6406/csln.html
Goodman. Algebra Abstract and Concrete. url:
http://www.math.uiowa.edu/~goodman/algebrabook.dir/algebrab
ook.html