Fast construction of irreducible polynomials over finite fields
COUVEIGNES, Jean-Marc
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
COUVEIGNES, Jean-Marc
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
< Reduce
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Lithe and fast algorithmic number theory [LFANT]
Laboratoire International de Recherche en Informatique et Mathématiques Appliquées [LIRIMA]
Institut de Mathématiques de Bordeaux [IMB]
Language
en
Article de revue
This item was published in
Israel Journal of Mathematics. 2013, vol. 194, n° 1, p. 77-105
Springer
English Abstract
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+o(1)} \times (\log q)^{5+o(1)}$ ...Read more >
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+o(1)} \times (\log q)^{5+o(1)}$ elementary operations. The $o(1)$ in $d^{1+o(1)}$ is a function of $d$ that tends to zero when $d$ tends to infinity. And the $o(1)$ in $(\log q)^{5+o(1)}$ is a function of $q$ that tends to zero when $q$ tends to infinity. In particular, the complexity is quasi-linear in the degree $d$.Read less <
English Keywords
number theory
algebraic geometry
Origin
Hal imported