Fast construction of irreducible polynomials over finite fields - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Israel Journal of Mathematics Année : 2013

Fast construction of irreducible polynomials over finite fields

Résumé

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$.
Fichier principal
Vignette du fichier
0905.1642v3.pdf (288.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00456456 , version 1 (09-10-2015)

Identifiants

Citer

Jean-Marc Couveignes, Reynald Lercier. Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 2013, 194 (1), pp.77-105. ⟨10.1007/s11856-012-0070-8⟩. ⟨hal-00456456⟩
486 Consultations
1232 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More