Fast construction of irreducible polynomials over finite fields

DOI10.1007/S11856-012-0070-8MaRDI QIDQ5917943zbMATH OpenOpenAlexFDO

Authors Jean-Marc Couveignes, Reynald Lercier

Publication date 18 June 2013

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.1642

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: 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+epsilon(d)}imes(logq{)}^{5+epsilon(q)}$ elementary operations. The function $epsilon$ 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+epsilon(d)}imes(logq{)}^{1+epsilon(q)}$ elementary operations only.

Recommendations

• Fast construction of irreducible polynomials over finite fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• scientific article; zbMATH DE number 437575
• Constructing irreducible polynomials over finite fields
• Finding irreducible and primitive polynomials

Cites work

• Abelian varieties over finite fields
• Analysis of Ben-Or's polynomial irreducibility test
• Complex multiplication structure of elliptic curves
• Factoring integers with elliptic curves
• Fast computation of special resultants
• Finding Isomorphisms Between Finite Fields
• scientific article; zbMATH DE number 437575 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3937328 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1748084 (Why is no real title available?)
• scientific article; zbMATH DE number 203033 (Why is no real title available?)
• ON THE PROBLEM OF JACOBSTHAL
• Remarque sur une formule de Shimura-Taniyama

Cited in

(22)

• Characterization and enumeration of good punctured polynomials over finite fields
• Fast reduction of algebraic lattices over cyclotomic fields
• On the complexity exponent of polynomial system solving
• Efficient indexing of necklaces and irreducible polynomials over finite fields
• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• scientific article; zbMATH DE number 437575 (Why is no real title available?)
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• scientific article; zbMATH DE number 5733040 (Why is no real title available?)
• Genus 2 point counting over prime fields
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• Computing isomorphisms and embeddings of finite fields
• scientific article; zbMATH DE number 3997938 (Why is no real title available?)
• Fast computation of elliptic curve isogenies in characteristic two
• Fast construction of irreducible polynomials over finite fields
• Elimination ideal and bivariate resultant over finite fields
• Breaking SIDH in polynomial time
• Iterative constructions of irreducible polynomials from isogenies
• Bivariate polynomial reduction and elimination ideal over finite fields
• Algorithms for computing norms and characteristic polynomials on general Drinfeld modules
• Modular composition via factorization
• Multiplication in finite fields with Chudnovsky-type algorithms over the projective line
• Pseudo-deterministic construction of irreducible polynomials over finite fields

This page was built for publication: Fast construction of irreducible polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917943)