constructing finite fields

[Chip Eastham]

In connection with a covering design problem posted here recently,
I wanted to construct some geometries over finite fields. Naturally
I got distracted by representing finite fields themselves.

My first thought was the usual quotient ring F[X]/(f) where F is the
finite field Z/pZ for prime p and f(X) is an irreducible polynomial of
degree n over F, yielding a field with p^n elements. It's not
terribly
hard to generate random guesses and test for irreducibility, but
it would seem that we are going somewhat out of our way with
this approach.

What I mean is that all finite fields with prime power p^n elements
are isomorphic, so one would hope that it could be constructed
effectively without the "arbitrary" choice of a particular irreducible
polynomial of degree n.

regards, chip

[I.M. Soloveichik]

one way is to take the splitting field for the polynomial
x^q-x when q=p^n.

[David Bernier]

I don't know anything about efficient construction other
than the usual F(X)/(f) approach.

Irreducible trinomials for the field with 2^n, and n is a
Mersenne prime, are of interest for pseudo-random number generation.
I think this is related to the Mersenne Twister algorithm.

Some readers might be interested in record degree irreducible
trinonials for F_{2^n}, n some Mersenne prime.

See e.g. Richard Brent's page
< http://wwwmaths.anu.edu.au/~brent/trinom.html >

David Bernier

--
Posted via a free Usenet account from http://www.teranews.com

[Pubkeybreaker]

What do you mean by "constructed effectively"???

The choice of basis can affect the time it takes to perform
computatations in
the field. For example, consider the time to multiply two elements.
For
an arbitrary basis, the best that can be done is a formal
multiplication of
the elemtns without carries (i.e. as polynomials), then to do a
reduction
modulo (f). This is expensive. It can be done much faster when you
use a
normal basis, and for some fields, one can construct an "optimal
normal basis"
which minimizes the number of primitive computations needed in (say)
multiplying
two elements. This is very useful in crypto applications. Look up
"ONB".

It is also better to use not just an irreducible polynomial of the
correct
degree, but also a *primitive* one (i.e. whose powers generate the
field)

See the Handbook of Applied Crytography for a discussion. Or consult
Lidl &
Neiderreiter's book.

[Timothy Murphy]

Chip Eastham wrote:

> What I mean is that all finite fields with prime power p^n elements
> are isomorphic, so one would hope that it could be constructed
> effectively without the "arbitrary" choice of a particular irreducible
> polynomial of degree n.

My impression is that people trying to save time
generally use a "normal basis",
that is, a basis consisting of n conjugate elements
(ie elements c, phi c, phi^2c, ... phi^{n-1}c,
where phi is the Frobenius automorphism x -> x^p).
But I'm no expert.

--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland

[Chip Eastham]

On Jan 2, 1:28 pm, "I.M. Soloveichik" <ims...@sbcglobal.net> wrote:
> one way is to take the splitting field for the polynomial
> x^q-x when q=p^n.

This is a nice characterization of the finite field
of q = p^n elements, but I cannot see how to apply
it effectively to perform actual field computations.

regards, chip

[Chip Eastham]

Thanks for the reference; I am one such interested
reader with respect to TLP (Tausworthe-Lewis-Payne)
generators.

--c

[Chip Eastham]

On Jan 2, 2:42 pm, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
> On Jan 2, 12:19 pm, Chip Eastham <hardm...@gmail.com> wrote:
>
>
>
> > In connection with a covering design problem posted here recently,
> > I wanted to construct some geometries over finite fields. Naturally
> > I got distracted by representing finite fields themselves.
>
> > My first thought was the usual quotient ring F[X]/(f) where F is the
> > finite field Z/pZ for prime p and f(X) is an irreducible polynomial of
> > degree n over F, yielding a field with p^n elements. It's not
> > terribly
> > hard to generate random guesses and test for irreducibility, but
> > it would seem that we are going somewhat out of our way with
> > this approach.
>
> > What I mean is that all finite fields with prime power p^n elements
> > are isomorphic, so one would hope that it could be constructed
> > effectively without the "arbitrary" choice of a particular irreducible
> > polynomial of degree n.

Pubkeybreaker wrote:

> What do you mean by "constructed effectively"???

That it affords representation of field elements with
at least conventionally rapid field arithmetic. The
geometries require linear algebra over the field.

> The choice of basis can affect the time it takes to perform
> computatations in the field. For example, consider the time
> to multiply two elements.
> For an arbitrary basis, the best that can be done is a formal

> multiplication of the elements without carries (i.e. as

> polynomials), then to do a reduction modulo (f). This is
> expensive. It can be done much faster when you use a
> normal basis, and for some fields, one can construct an
> "optimal normal basis" which minimizes the number of primitive
> computations needed in (say) multiplying two elements. This
> is very useful in crypto applications. Look up "ONB".

Thanks, I'll look into it.

> It is also better to use not just an irreducible polynomial
> of the correct degree, but also a *primitive* one (i.e. whose
> powers generate the field)

Thanks, I wasn't familiar with the notion of a primitive
irreducible polynomial f, meaning (in context) that the
image X mod f is a primitive element of the field F[X]/(f).

regards, chip

[Chip Eastham]

Thanks, it seems to tie in with the suggestions of
David Bernier and Pubkeybreaker above and gives me
some additional search terms to look for.

regards, chip

[Derek Holt]

In addition to the suggestions made so far, you could also consider
Conway polynomials. This is a completely different usage from the one
in Knot Theory. See,for example:

http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol/index.html

The Conway polynomial is the least primitive polynomial for the field
under a certain somewhat arbitrary ordering, but also subject to the
condition that the chosen primitive elements restrict sensibly to
subfields. (For example, raising a root of the Conway polynomial for
GF(p^4) to the power p^2+1 must give a root of the Conway polynomial
of GF(p^2).)

The main advantage of using Conway polynomials is that they facilitate
communication between different systems and different users when
exchanging data. Unfortunately, they have to be computed individually
for each finite field, and this grows more difficult as the field
grows larger, so they cannot be used for very large fields.

Derek Holt.