A New Algorithm for Factoring Polynomials Over Finite Fields

DOI10.2307/2007663zbMATH Open0493.12024OpenAlexW4231623775MaRDI QIDQ3955477FDOQ3955477

Authors: David G. Cantor, H. Zassenhaus 

Publication date: 1981

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

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

zbMATH Keywords

probabilistic methodfactorization of polynomials

Mathematics Subject Classification ID

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

Cites Work

• Factoring Polynomials Over Large Finite Fields
• Probabilistic Algorithms in Finite Fields
• On the Efficiency of Algorithms for Polynomial Factoring
• Title not available (Why is that?)
• An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials over GF(p)
• Title not available (Why is that?)

Cited In (97)

• On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\)
• Implementing the tangent Graeffe root finding method
• A Highly Scalable RFID Authentication Protocol
• Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
• On a family of preimage-resistant functions
• Computing primitive idempotents in finite commutative rings and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing isomorphisms and embeddings of finite fields
• Deterministic root finding in finite fields
• Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\)
• The Rabin cryptosystem revisited
• Succinct non-interactive arguments via linear interactive proofs
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• \textsc{Rings}: an efficient Java/Scala library for polynomial rings
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Towards a quantum-resistant weak verifiable delay function
• A new approach for finding low-weight polynomial multiples
• Efficiently factoring polynomials modulo \(p^4\)
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Isogeny problems with level structure
• A generalized successive resultants algorithm
• Limits on the power of prime-order groups: separating Q-type from static assumptions
• Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
• 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
• 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
• On arithmetical algorithms over finite fields
• Fast rectangular matrix multiplication and applications
• The black-box Niederreiter algorithm and its implementation over the binary field
• On the complementary factor in a new congruence algorithm
• Title not available (Why is that?)
• Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields
• Factoring polynomials using fewer random bits
• Computing conjugating sets and automorphism groups of rational functions
• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• Factoring Multivariate Polynomials over Large Finite Fields
• Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields
• Factoring polynomials over finite fields with Drinfeld modules
• Factoring polynomials over local fields.
• Optimal forgeries against polynomial-based MACs and GCM
• Cryptographic applications of capacity theory: on the optimality of Coppersmith's method for univariate polynomials
• Computing Frobenius maps and factoring polynomials
• A new efficient factorization algorithm for polynomials over small finite fields
• Explicit equivalence of quadratic forms over \(\mathbb{F}_q(t)\)
• Factoring multivariate polynomials via partial differential equations
• Title not available (Why is that?)
• On the deterministic complexity of factoring polynomials over finite fields
• Computing explicit isomorphisms with full matrix algebras over \(\mathbb {F}_q(x)\)
• Is every matrix similar to a polynomial in a companion matrix?
• Deterministic root finding over finite fields using Graeffe transforms
• Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
• Interval partitions and polynomial factorization
• On the computation of rational points of a hypersurface over a finite field
• Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
• Computer construction of split Cartan subalgebras
• Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields
• Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
• Kronecker's and Newton's approaches to solving: a first comparison
• A public key cryptosystem based on Diophantine equations of degree increasing type
• Are fifth-degree equations over \(GF(5^ m)\) solvable by radicals?
• On algorithms to find \(p\)-ordering
• New Sparse Multivariate Polynomial Factorization Algorithms over Integers
• Univariate polynomial factorization over finite fields
• Decomposition of algebras over finite fields and number fields
• A note on Gröbner bases and Berlekamp's algorithm
• Factoring polynomials over finite fields: A survey
• On a New Factorization Algorithm for Polynomials Over Finite Fields
• On splitting sets in block designs and finding roots of polynomials
• Towards a soluble quotient algorithm
• Factoring polynomials and primitive elements for special primes
• A heuristic irreducibility test for univariate polynomials
• Analysis of Euclidean algorithms for polynomials over finite fields
• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Testing isomorphism of graded algebras
• Using partial smoothness of \(p-1\) for factoring polynomials modulo \(p\)
• Distinct Degree Factorizations for Polynomials over a Finite Field
• A generalisation of the Cantor-Zassenhaus algorithm
• Trading GRH for algebra: algorithms for factoring polynomials and related structures
• Subquadratic-time factoring of polynomials over finite fields
• The complete analysis of a polynomial factorization algorithm over finite fields
• Deterministic irreducibility testing of polynomials over large finite fields
• Polynomial factorization over ${\mathbb F}_2$
• Factoring polynomials over finite fields
• Short presentations for finite groups
• On Bivariate Polynomial Factorization over Finite Fields
• On the degrees of irreducible factors of polynomials over a finite field
• Algebraic algorithms in GF(q)
• On the Complexity of the Montes Ideal Factorization Algorithm
• Computing the structure of finite algebras
• Polynomial factorization algorithms over number fields
• Computing special powers in finite fields
• Iterative root approximation in \(p\)-adic numerical analysis
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

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)