4
$\begingroup$

I'm playing around with finite field arithmetic and implementing it in a little library. I'd like to be able to handle arbitrary finite fields given their size and characteristic. I don't want to write down a prime polynomial for every given possible finite field though. How can I generate a prime polynomial of a given degree for use in multiplication? To be clear I don't care which polynomial I get, and I don't want all of them. I just want any old one of a given degree. If this is an open research question what if we only try to solve it for $GF(2^n)$?

$\endgroup$
2
$\begingroup$

It suffices to construct an irreducible polynomial of degree $n$ over $GF(2)$ (as this immediately induces an explicit construction for $GF(2^n)$). So, how do you generate an irreducible polynomial?

One approach is to repeatedly choose a random polynomial of degree $n$, then test whether it is irreducible. You can test for irreducibility by factoring the polynomial over $GF(2)$. There are standard algorithms for polynomial factorization; they run in polynomial time. Moreover, about a $1/n$ fraction of all polynomials are irreducible (see here). It follows that on average about $n$ iterations will suffice, and since each iteration can be done in polynomial time, the whole thing runs in (randomized) polynomial time.

$\endgroup$
  • $\begingroup$ How do we know about 1/n are irreducible? I've read that in "fast construction of irreducible polynomials over finite fields" (well actually 1/2n but same difference). The reference hits a thick textbook though. $\endgroup$ – Jake Mar 8 '18 at 12:48
  • $\begingroup$ @Jake, the linked Wikipedia page gives a sketch of how to prove that 1/n of monic polynomials are irreducible. But multiplying by a constant doesn't change reducibility. $\endgroup$ – Peter Taylor Mar 8 '18 at 14:25
  • $\begingroup$ @PeterTaylor, indeed -- and moreover in this case, we are working over $GF(2)$, and all polynomials over $GF(2)$ are monic. $\endgroup$ – D.W. Mar 8 '18 at 16:33
  • 1
    $\begingroup$ Thinking about it, if you're working over $GF(2)$ and testing random polynomials you can easily improve the odds to $2/n$ by ensuring that you have an odd number of non-zero coefficients (i.e. don't select the constant coefficient randomly). $\endgroup$ – Peter Taylor Mar 8 '18 at 16:39
2
$\begingroup$

In a related question on MathOverflow, Igor Rivin provides a link to a 2009 pre-print of a paper of Couveignes and Lercier, Fast construction of irreducible polynomials over finite fields, which uses elliptic curves to provide a probabilistic quasi-linear algorithm. The paper was published in Israel Journal of Mathematics (2013) vol. 194, pp 77–105, DOI https://doi.org/10.1007/s11856-012-0070-8

$\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.