A New Algorithm for Factoring Polynomials Over Finite Fields

DOI10.2307/2007663MaRDI QIDQ3955477zbMATH OpenOpenAlexFDO

Authors David G. Cantor, H. Zassenhaus

Publication date 1981

Full work available at URL https://doi.org/10.2307/2007663

zbMATH Keywords

factorization of polynomialsprobabilistic method

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Software, source code, etc. for problems pertaining to field theory (12-04) Polynomials in general fields (irreducibility, etc.) (12E05) Algorithms in computer science (68W99)

Recommendations

• On a New Factorization Algorithm for Polynomials Over Finite Fields
• scientific article; zbMATH DE number 691482
• A new efficient factorization algorithm for polynomials over small finite fields
• scientific article; zbMATH DE number 1594303
• Polynomial factorization algorithms over number fields
• A new polynomial factorization algorithm and its implementation
• An efficient algorithm for factoring polynomials over algebraic extension field
• A new faster algorithm for factoring skew polynomials over finite fields
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Factoring polynomials over arbitrary finite fields

Cites work

• An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials over GF(p)
• Factoring Polynomials Over Large Finite Fields
• scientific article; zbMATH DE number 3557181 (Why is no real title available?)
• scientific article; zbMATH DE number 3341170 (Why is no real title available?)
• On the Efficiency of Algorithms for Polynomial Factoring
• Probabilistic Algorithms in Finite Fields

Cited in

(only showing first 100 items - show all)

• Iterative root approximation in \(p\)-adic numerical analysis
• Algebraic algorithms in GF(q)
• On the complementary factor in a new congruence algorithm
• Factoring polynomials and primitive elements for special primes
• Towards a soluble quotient algorithm
• Univariate polynomial factorization over finite fields
• A heuristic irreducibility test for univariate polynomials
• Fast rectangular matrix multiplication and applications
• On the degrees of irreducible factors of polynomials over a finite field
• Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
• Short presentations for finite groups
• A generalisation of the Cantor-Zassenhaus algorithm
• Explicit equivalence of quadratic forms over \(\mathbb{F}_q(t)\)
• Optimal forgeries against polynomial-based MACs and GCM
• Computing explicit isomorphisms with full matrix algebras over \(\mathbb {F}_q(x)\)
• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Deterministic irreducibility testing of polynomials over large finite fields
• Are fifth-degree equations over \(GF(5^ m)\) solvable by radicals?
• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields
• Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
• Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\)
• Succinct non-interactive arguments via linear interactive proofs
• A new approach for finding low-weight polynomial multiples
• One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model
• Efficiently factoring polynomials modulo \(p^4\)
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• The Rabin cryptosystem revisited
• On the computation of rational points of a hypersurface over a finite field
• Computing Frobenius maps and factoring polynomials
• A new efficient factorization algorithm for polynomials over small finite fields
• Interval partitions and polynomial factorization
• Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields
• A note on Gröbner bases and Berlekamp's algorithm
• Computing the structure of finite algebras
• Polynomial factorization algorithms over number fields
• Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
• The complete analysis of a polynomial factorization algorithm over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
• Cryptographic applications of capacity theory: on the optimality of Coppersmith's method for univariate polynomials
• Deterministic root finding over finite fields using Graeffe transforms
• On a family of preimage-resistant functions
• Trading GRH for algebra: algorithms for factoring polynomials and related structures
• Polynomial factorization over ${\mathbb F}_2$
• Using partial smoothness of p-1 for factoring polynomials modulo p
• scientific article; zbMATH DE number 6500356 (Why is no real title available?)
• Factoring Multivariate Polynomials over Large Finite Fields
• Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields
• A Highly Scalable RFID Authentication Protocol
• scientific article; zbMATH DE number 1273636 (Why is no real title available?)
• scientific article; zbMATH DE number 1303020 (Why is no real title available?)
• On a New Factorization Algorithm for Polynomials Over Finite Fields
• Subquadratic-time factoring of polynomials over finite fields
• The black-box Niederreiter algorithm and its implementation over the binary field
• Factoring polynomials over finite fields with Drinfeld modules
• Is every matrix similar to a polynomial in a companion matrix?
• Computing isomorphisms and embeddings of finite fields
• Factoring multivariate polynomials via partial differential equations
• Computing conjugating sets and automorphism groups of rational functions
• Computing special powers in finite fields
• Distinct Degree Factorizations for Polynomials over a Finite Field
• On the Complexity of the Montes Ideal Factorization Algorithm
• Factoring polynomials over finite fields
• Implementing the tangent Graeffe root finding method
• Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
• Testing isomorphism of graded algebras
• A generalized successive resultants algorithm
• Deterministic root finding in finite fields
• On Bivariate Polynomial Factorization over Finite Fields
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Factoring polynomials over finite fields: A survey
• Kronecker's and Newton's approaches to solving: a first comparison
• Factoring polynomials over local fields.
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• New Sparse Multivariate Polynomial Factorization Algorithms over Integers
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
• Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\)
• Univariate polynomial factorization over finite fields with large extension degree
• Computing primitive idempotents in finite commutative rings and applications
• \textsc{Rings}: an efficient Java/Scala library for polynomial rings
• Computing a group action from the class field theory of imaginary hyperelliptic function fields
• Solving polynomial systems over non-fields and applications to modular polynomial factoring
• On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\)
• Towards a quantum-resistant weak verifiable delay function
• Isogeny problems with level structure
• Limits on the power of prime-order groups: separating Q-type from static assumptions
• Multivariate encryptions with LL' perturbations. Is it possible to repair HFE in encryption? When 0 makes a difference
• Decomposition of algebras over finite fields and number fields
• A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
• Singular points of UOV and VOX
• Gröbner basis cryptanalysis of Anemoi
• Sparse polynomial interpolation: faster strategies over finite fields
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• Space-lock puzzles and verifiable space-hard functions from root-finding in sparse polynomials
• Modelling ciphers with overdefined systems of quadratic equations: application to Friday, Vision, RAIN and Biscuit
• A univariate attack against the limited-data instance of Ciminion
• Factoring sparse polynomials fast
• State of the art of HFE variants. Is it possible to repair HFE with appropriate modifiers?

This page was built for publication: A New Algorithm for Factoring Polynomials Over Finite Fields

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