Univariate polynomial factorization over finite fields

DOI10.1016/S0304-3975(97)80001-1zbMath0914.11064MaRDI QIDQ1127311

Claude Quitté, Patrice Naudin

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite fieldspolynomial factorizationBerlekamp algorithmCantor-Zassenhaus algorithm

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06)

Related Items

Fast rectangular matrix multiplication and some applications, Factoring polynomials over finite fields: A survey, Factoring polynomials over arbitrary finite fields

Uses Software

• AXIOM
• FAST16
• GALOIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials modulo special primes
• On arithmetical algorithms over finite fields
• On the deterministic complexity of factoring polynomials over finite fields
• Factoring polynomials in finite fields: An application of Lang-Weil to a problem in graph theory
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Algebraic algorithms in GF(q)
• Factorization of polynomials over a finite field and the solution of systems of algebraic equations
• Computing roots of polynomials on vector processing machines
• Factoring polynomials and primitive elements for special primes
• Factorization of polynomials over finite fields
• Arithmetic of finite fields
• Smoothness and factoring polynomials over finite fields
• Computational problems in the theory of finite fields
• On fast multiplication of polynomials over arbitrary algebras
• The Chinese remainder theorem
• Counting irreducible factors of polynomials over a finite field
• Note on cubics over \(GF(2^n)\) and \(GF(3^n)\)
• Algorithms related to the decomposition of polynomials
• An analog to the discriminant over fields of characteristic two
• Factorization over a finite field \(\mathbb F_{p^n}\) of the composite polynomials \(f\left(X^{p^r}-aX\right)\) where \(f(X)\) is an irreducible polynomial in \(\mathbb F_{p^n}(X)\)
• Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
• Factorization of polynomials and some linear-algebra problems over finite fields
• Finding irreducible and primitive polynomials
• Factorization of polynomials over finite fields and characteristic sequences
• Factoring of \(x^ n -1\) and orthogonalization over finite fields of characteristic 2
• Square-free algorithms in positive characteristic
• A new polynomial factorization algorithm and its implementation
• On the Chor-Rivest knapsack cryptosystem
• Computing Frobenius maps and factoring polynomials
• A new efficient factorization algorithm for polynomials over small finite fields
• On the factorization of polynomials
• On Hensel factorization. I
• On the computational power of pushdown automata
• Separable algebras over commutative rings
• Irreducibility Testing and Factorization of Polynomials
• How to share a secret
• Effective procedures in field theory
• ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
• A Generalized Class of Polynomials that are Hard to Factor
• Finding the number of factors of a polynomial
• Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme
• On the continued fraction and Berlekamp's algorithm (Corresp.)
• Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
• Multiplication of Polynomials over Finite Fields
• Finding Isomorphisms Between Finite Fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
• A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
• Solving sparse linear equations over finite fields
• On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
• When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• New directions in cryptography
• Factorization of univariate polynomials
• Arithmetic in a Finite Field
• Probabilistic Algorithms in Finite Fields
• On Polynomial Factorization Over Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Searching for Primitive Roots in Finite Fields
• On the Distribution of Quadratic Residues and Nonresidues Modulo a Prime Number
• Solving equations in finite fields and some results concerning the structure of GF(p/sup m/)
• Galois Groups and Factoring Polynomials over Finite Fields
• Primitive Polynomials Over Finite Fields
• Computing in GF(q)
• On the Efficiency of Algorithms for Polynomial Factoring
• Constructions in Algebra
• A method for obtaining digital signatures and public-key cryptosystems
• On the Efficiency of a Polynomial Irreducibility Test
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• A Remark on the Hensel Factorization Method
• Factoring Polynomials over a Finite Field
• Computing Gretest Common Divisors and Factorizations in Quadratic Number Fields
• A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(p^m) of GF(p), p a Small Prime
• Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases
• An Acceleration of the Niederreiter Factorization Algorithm in Characteristic 2
• On a New Factorization Algorithm for Polynomials Over Finite Fields
• Computer Algebra of Polynomials and Rational Functions
• A geometric approach to root finding in GT(q/sup m/)
• Un Algorithme De Construction Des Idempotents Primitifs D'Ideaux D'Algebres Sur Fq
• Statistics on factoring polynomials mod p and p-adically
• Distinct Degree Factorizations for Polynomials over a Finite Field
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• On the Quadratic Character of a Polynomial
• Computable Algebra, General Theory and Theory of Computable Fields
• The Factorization of the Cyclotomic Polynomials mod p
• On the solution of algebraic equations over finite fields
• Factorization of Polynomials Over Finite Fields
• Factoring Polynomials Over Large Finite Fields
• A note on square roots in finite fields
• ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
• Hiding information and signatures in trapdoor knapsacks
• Fast construction of irreducible polynomials over finite fields