Fast construction of irreducible polynomials over finite fields

作     者：Couveignes, Jean-Marc Lercier, Reynald 

作者机构：INRIA Bordeaux Sud Ouest F-31058 Toulouse 9 France Univ Toulouse 2 Univ Toulouse Dept Math & Informat F-31058 Toulouse 9 France DGA F-35174 La Roche Marguerite France Univ Rennes 1 Inst Rech Math Rennes F-35042 Rennes France 

出 版 物：《ISRAEL JOURNAL OF MATHEMATICS》 (以色列数学杂志)

年 卷 期：2013年第194卷第1期

页      面：77-105页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：randomized belonging polynomial Galois fields randomized algorithms Polynomial Belonging Irreducible Irreducible polynomial RANDOMISING Elementary 

摘      要：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+E (d))x(log q)(5+E (q)) elementary operations. The function E 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+E (d)) x (log q)(1+E (q)) elementary operations only.