COUVEIGNES, Jean-Marc; LERCIER, Reynald

doi:10.1007/s11856-012-0070-8

Métadonnées

Licence d’utilisation du document

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]

LERCIER, Reynald
Institut de Recherche Mathématique de Rennes [IRMAR]

Langue

Article de revue

Ce document a été publié dans

Israel Journal of Mathematics. 2013, vol. 194, n° 1, p. 77-105

Springer

Résumé en anglais

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$.< Réduire

Mots clés en anglais

number theory

algebraic geometry

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Fast construction of irreducible polynomials over finite fields

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche