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.NEWLINENEWLINENEWLINEThe 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.NEWLINENEWLINENEWLINEThe 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.NEWLINENEWLINENEWLINEMany general factoring algorithms comprise the following three steps:NEWLINENEWLINENEWLINESFF: square free factorization that reduces the given polynomial to one which contains all the irreducible factors to degree one. NEWLINENEWLINENEWLINEDDF: 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
- 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 1008373 (Why is no real title available?)
- scientific article; zbMATH DE number 1361739 (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}\)
- 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)
