Reynald Lercier

J.-M. Couveignes et R. Lercier. Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, pages 1-29, Mai 2012.

Nous proposons un algorithme randomisé qui sur entrée d'un corps fini K avec q éléments et un entier strictement positif d retourne un polynôme irréductible de degré d dans K[x]. Le temps d'exécution est d^1+ε(d) ×(logq)^5+ε(q) opérations élémentaires. La fonction ε dans cette expression est une fonction réelle positive appartenant à la classe o(1), en particulier, la complexité est quasi-linéaire en d. Étant donné un polynôme irréductible de degré d, on peut calculer un polynôme irréductible aléatoire de degré d au prix de d^1+ε(d) ×(logq)^1+ε(q) opérations élémentaires.

[ bib | preprint | publication ] Retour