12
$\begingroup$

I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then obtain the field as its quotient ring), but how can such polynomial be efficiently found?

Also, I know there are more ways to represent elements of finite fields - are they easier to use than the irreducible polynomial method? What is done in practice in computational mathematical libraries?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Regarding the last question, I think in practice libraries store explicit irreducible polynomials in a range of practical interest ($p = 2$ and $n = $...?). Regarding the first, perhaps one can try applying Cantor-Zassenhaus to $x^q - x$? What sizes of $p$ and $n$ are you interested in? If $n$ is small compared to $p$ perhaps you can get away with writing down a random polynomial and using some efficient primality tests... $\endgroup$ – Qiaochu Yuan Jul 16 '11 at 6:19
  • 1
    $\begingroup$ I think that the best way of representing elements of finite fields depends on what type of operations you want to perform with them. If you do a lot of Frobenius automorphisms (read: squaring in a field of char 2), then an optimal normal basis might be best. If your field is relatively small, then you may want to store the entire field as a table. Using either a logarithm table or a Zech logarithm table will convert field arithmetic to integer arithmetic. $\endgroup$ – Jyrki Lahtonen Jul 16 '11 at 7:17
  • 1
    $\begingroup$ Sage has a decent implementation of finite fields see here. $\endgroup$ – JSchlather Jul 16 '11 at 17:53
5
$\begingroup$

In practice, one guesses an $n$'th degree polynomial and tests it for irreducibility. As a random polynomial has about a $1/n$ probability of being irreducible, this does not take too long. For variations and improvements on this idea see this paper by Shoup (author of the NTL library, which you may also want to look at.)

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.