naa a22 4500 510783287 CHVBK 20180411083254.0 cr unu---uuuuu 180411e20130301xx s 000 0 eng 10.1007/s11856-012-0070-8 doi (NATIONALLICENCE)springer-10.1007/s11856-012-0070-8 Fast construction of irreducible polynomials over finite fields [Elektronische Daten] [Jean-Marc Couveignes, Reynald Lercier] We present a randomized algorithm that on inputting 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+ɛ(d)×(log q)5+ɛ(q) elementary operations. The function ɛ 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+ɛ(d) × (log q)1+ɛ(q) elementary operations only. Hebrew University Magnes Press, 2012 Couveignes Jean-Marc INRIA Bordeaux Sud-Ouest & Université de Toulouse, Université de Toulouse le Mirail, Département de Mathématiques et Informatique, 5 allées Antonio Machado, F-31058, Toulouse cédex 9, France aut Lercier Reynald La Roche Marguerite, DGA, F-35174, Bruz Cedex, France aut Israel Journal of Mathematics The Hebrew University Magnes Press 194/1(2013-03-01), 77-105 0021-2172 194:1<77 2013 194 11856 https://doi.org/10.1007/s11856-012-0070-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11856-012-0070-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Couveignes Jean-Marc INRIA Bordeaux Sud-Ouest & Université de Toulouse, Université de Toulouse le Mirail, Département de Mathématiques et Informatique, 5 allées Antonio Machado, F-31058, Toulouse cédex 9, France aut NATIONALLICENCE 700 1- Lercier Reynald La Roche Marguerite, DGA, F-35174, Bruz Cedex, France aut NATIONALLICENCE 773 0- Israel Journal of Mathematics The Hebrew University Magnes Press 194/1(2013-03-01), 77-105 0021-2172 194:1<77 2013 194 11856 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer