Factoring polynomials over finite fields: A survey
From MaRDI portal
The paper surveys several algorithms for the factorization of univariate polynomials over finite fields, emphasizing the main ideas of the methods. The problem addressed is: Given a monic univariate polynomial \(f\in F_q [x]\), find the complete factorization \(f = f_1^{e_1} f_2^{e_2}\cdots f_k^{e_k}\) where \(f_1,\dots,f_k\) are pairwise distinct monic irreducible polynomials and \(e_1,\dots,e_k\) are positive integers. The complexity of the algorithms discussed are given in terms of the number of operations in \({F}_q\) and the ``soft \(O\) notation is used that ignores logarithmic factors. Some discussion is given of the practicality of fast arithmetic and matrix arithmetic. Many general factoring algorithms comprise the following three steps: SFF: square free factorization that reduces the given polynomial to one which contains all the irreducible factors to degree one. DDF: distinct degree factorization splits the squarefree polynomial into a product of polynomials whose irreducible factors all have the same degree.
Recommendations
Cites work
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(pm) of GF(p), p a Small Prime
- A Fast Monte-Carlo Test for Primality
- A geometric approach to root finding in GT(q/sup m/)
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- A New Algorithm for Factoring Polynomials Over Finite Fields
- A new efficient factorization algorithm for polynomials over small finite fields
- A new polynomial factorization algorithm and its implementation
- Algorithmic number theory. 3rd international symposium, ANTS-III, Portland, OR, USA, June 21--25, 1998. Proceedings
- An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials over GF(p)
- Analysis of Ben-Or's polynomial irreducibility test
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- Computational Complexity of Probabilistic Turing Machines
- Computing Frobenius maps and factoring polynomials
- Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
- Counting irreducible factors of polynomials over a finite field
- Counting polynomials with a given number of zeros in a finite field
- Deterministic analysis of aleatoric methods of polynomial factorization over finite fields
- Deterministic irreducibility testing of polynomials over large finite fields
- Distinct Degree Factorizations for Polynomials over a Finite Field
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Equations over finite fields. An elementary approach
- Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2
- Factoring polynomials and primitive elements for special primes
- Factoring polynomials modulo special primes
- Factoring Polynomials over a Finite Field
- Factoring polynomials over arbitrary finite fields
- Factoring polynomials over finite fields
- Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials using fewer random bits
- Factoring polynomials with rational coefficients
- Factorization of polynomials and some linear-algebra problems over finite fields
- Factorization of Polynomials Over Finite Fields
- Factorization of polynomials over finite fields and characteristic sequences
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Factorization of the General Polynomial by Means of Its Homomorphic Congruential Functions
- 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)\)
- Fast construction of irreducible polynomials over finite fields
- Fast multiplication of large numbers
- Fast multiplication of polynomials over fields of characteristic 2
- Fast rectangular matrix multiplication and applications
- Finding irreducible and primitive polynomials
- Finite fields: theory and computation. The meeting point of number theory, computer science, coding theory and cryptography
- Galois Groups and Factoring Polynomials over Finite Fields
- Generalized riemann hypothesis and factoring polynomials over finite fields
- scientific article; zbMATH DE number 988157 (Why is no real title available?)
- scientific article; zbMATH DE number 4173143 (Why is no real title available?)
- scientific article; zbMATH DE number 3169494 (Why is no real title available?)
- scientific article; zbMATH DE number 4152517 (Why is no real title available?)
- scientific article; zbMATH DE number 3823145 (Why is no real title available?)
- scientific article; zbMATH DE number 3956969 (Why is no real title available?)
- scientific article; zbMATH DE number 4065121 (Why is no real title available?)
- scientific article; zbMATH DE number 4069025 (Why is no real title available?)
- scientific article; zbMATH DE number 3658967 (Why is no real title available?)
- scientific article; zbMATH DE number 3706379 (Why is no real title available?)
- scientific article; zbMATH DE number 3717441 (Why is no real title available?)
- scientific article; zbMATH DE number 3763833 (Why is no real title available?)
- scientific article; zbMATH DE number 15339 (Why is no real title available?)
- scientific article; zbMATH DE number 3517269 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3578960 (Why is no real title available?)
- scientific article; zbMATH DE number 3608160 (Why is no real title available?)
- scientific article; zbMATH DE number 3637278 (Why is no real title available?)
- scientific article; zbMATH DE number 1222349 (Why is no real title available?)
- scientific article; zbMATH DE number 1222356 (Why is no real title available?)
- scientific article; zbMATH DE number 691468 (Why is no real title available?)
- scientific article; zbMATH DE number 691482 (Why is no real title available?)
- scientific article; zbMATH DE number 953213 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3304871 (Why is no real title available?)
- scientific article; zbMATH DE number 3318360 (Why is no real title available?)
- scientific article; zbMATH DE number 3379035 (Why is no real title available?)
- scientific article; zbMATH DE number 3389111 (Why is no real title available?)
- Hybrid methods for finding roots of a polynomial - With application to BCH decoding (Corresp.)
- Idempotent computation over finite fields
- Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
- Matrix multiplication via arithmetic progressions
- Modern computer algebra
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- On a New Factorization Algorithm for Polynomials Over Finite Fields
- On arithmetical algorithms over finite fields
- On Bivariate Polynomial Factorization over Finite Fields
- On fast multiplication of polynomials over arbitrary algebras
- On Hensel factorization. I
- On Polynomial Factorization Over Finite Fields
- On the Chor-Rivest knapsack cryptosystem
- On the computational power of pushdown automata
- On the deterministic complexity of factoring polynomials
- On the deterministic complexity of factoring polynomials over finite fields
- On the Efficiency of Algorithms for Polynomial Factoring
- On the number of irreducible factors of a polynomial over a finite field
- On the number of roots and irreducible factors of a given congruence
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- Probabilistic Algorithms in Finite Fields
- Smoothness and factoring polynomials over finite fields
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- Solving sparse linear equations over finite fields
- Subgroup Refinement Algorithms for Root Finding in GF(q)
- Subquadratic-time factoring of polynomials over finite fields
- Subspaces and polynomial factorizations over finite fields
- Sur la factorisation des polynômes \(f(X^{p^{2r}}-aX^{p^r}-bX)\) sur un corps fini \(\mathbb{F}_{p^s}\)
- Tests and constructions of irreducible polynomials over finite fields
- Un Algorithme De Construction Des Idempotents Primitifs D'Ideaux D'Algebres Sur Fq
- Univariate polynomial factorization over finite fields
Cited in
(46)- Efficient \(p\)th root computations in finite fields of characteristic \(p\)
- Factoring polynomials over global fields
- Univariate polynomial factorization over finite fields
- On square-free factorization of multivariate polynomials over a finite field.
- On the last fall degree of zero-dimensional Weil descent systems
- Rigorous analysis of a randomised number field sieve
- Computing the bound of an Ore polynomial. Applications to factorization
- How to securely outsource the extended Euclidean algorithm for large-scale polynomials over finite fields
- Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
- Permutation polynomials and factorization
- Computation of orders and cycle lengths of automorphisms of finite solvable groups
- Random self-reducibility of ideal-SVP via Arakelov random walks
- Succinct non-interactive arguments via linear interactive proofs
- Efficiently factoring polynomials modulo \(p^4\)
- Computing Frobenius maps and factoring polynomials
- Interval partitions and polynomial factorization
- The index calculus method using non-smooth polynomials
- The complete analysis of a polynomial factorization algorithm over finite fields
- Sublinear root detection and new hardness results for sparse polynomials over finite fields
- Finding roots in \(\mathbb F_{p^n}\) with the successive resultants algorithm
- Algebraic cryptanalysis of Yasuda, Takagi and Sakurai's signature scheme
- Deterministic root finding over finite fields using Graeffe transforms
- Polynomial factorization over ${\mathbb F}_2$
- Last fall degree, HFE, and Weil descent attacks on ECDLP
- scientific article; zbMATH DE number 1254269 (Why is no real title available?)
- Complexity bounds for the rational Newton-Puiseux algorithm over finite fields
- Subquadratic-time factoring of polynomials over finite fields
- Computing special powers in finite fields
- A solution to certain polynomial equations with applications to nonlinear fitting
- Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
- Using zeta functions to factor polynomials over finite fields
- A generalized successive resultants algorithm
- The eigenstructure of finite field trigonometric transforms
- Multi-party updatable delegated private set intersection
- Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\)
- Computing primitive idempotents in finite commutative rings and applications
- A note on Gao's algorithm for polynomial factorization
- Solving polynomial systems over non-fields and applications to modular polynomial factoring
- Equal-degree factorization of binomials and trinomials over finite fields
- Efficient algorithms for finite \(\mathbb{Z}\)-algebras
- Towards a quantum-resistant weak verifiable delay function
- Structures of finite fields of primes and the Euclidean square roots of unity in the finite rings
- Structured ramp secret sharing schemata over rings of real polynomials
- Adaptively secure threshold blind BLS signatures and threshold oblivious PRF
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
- Fast rectangular matrix multiplication and some applications
This page was built for publication: Factoring polynomials over finite fields: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928877)
