Fast construction of irreducible polynomials over finite fields

Details Fast construction of irreducible polynomials over finite fields Fast construction of irreducible polynomials over finite fields

2009-05-11

arxiv.org/abs/0905.1642v3

Mathematics

Number Theory

To appear in the Israel Journal of Mathematics

Scientific paper

We present a randomized algorithm that on input a finite field $K$ with $q$ elements and a positive integer $d$ outputs a degree $d$ irreducible polynomial in $K[x]$. The running time is $d^{1+\epsilon(d)} \times (\log q)^{5+\epsilon(q)}$ elementary operations. The function $\epsilon$ in this expression is a real positive function belonging to the class $o(1)$, especially, the complexity is quasi-linear in the degree $d$. Once given such an irreducible polynomial of degree $d$, we can compute random irreducible polynomials of degree $d$ at the expense of $d^{1+\epsilon(d)} \times (\log q)^{1+\epsilon(q)}$ elementary operations only.

Affiliated with

Also associated with

No associations

Rating

Fast construction of irreducible polynomials over finite fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast construction of irreducible polynomials over finite fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast construction of irreducible polynomials over finite fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-701601