Factoring polynomials over finite fields: A survey
From MaRDI portal
Publication:5928877
DOI10.1006/jsco.1999.1002zbMath0969.11041DBLPjournals/jsc/GathenP01OpenAlexW2170368342WikidataQ56003479 ScholiaQ56003479MaRDI QIDQ5928877
Daniel Panario, Joachim von zur Gathen
Publication date: 20 September 2001
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jsco.1999.1002
Related Items (31)
Succinct non-interactive arguments via linear interactive proofs ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP ⋮ Computing special powers in finite fields ⋮ A solution to certain polynomial equations with applications to nonlinear fitting ⋮ Algebraic Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature Scheme ⋮ Multi-party updatable delegated private set intersection ⋮ On the last fall degree of zero-dimensional Weil descent systems ⋮ 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 ⋮ Interval partitions and polynomial factorization ⋮ A note on Gao's algorithm for polynomial factorization ⋮ Complexity bounds for the rational Newton-Puiseux algorithm over finite fields ⋮ Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity ⋮ The index calculus method using non-smooth polynomials ⋮ Fast rectangular matrix multiplication and some applications ⋮ Efficiently factoring polynomials modulo \(p^4\) ⋮ Rigorous analysis of a randomised number field sieve ⋮ How to securely outsource the extended Euclidean algorithm for large-scale polynomials over finite fields ⋮ Computing the bound of an Ore polynomial. Applications to factorization ⋮ The eigenstructure of finite field trigonometric transforms ⋮ Unnamed Item ⋮ Permutation polynomials and factorization ⋮ Efficient \(p\)th root computations in finite fields of characteristic \(p\) ⋮ Computation of orders and cycle lengths of automorphisms of finite solvable groups ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ Using zeta functions to factor polynomials over finite fields ⋮ Random self-reducibility of ideal-SVP via Arakelov random walks ⋮ A Generalised Successive Resultants Algorithm ⋮ Polynomial factorization over ${\mathbb F}_2$ ⋮ Finding roots in with the successive resultants algorithm
Uses Software
Cites Work
- Factoring Polynomials Over Large Finite Fields
- On the number of roots and irreducible factors of a given congruence
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- Fast construction of irreducible polynomials over finite fields
- On the deterministic complexity of factoring polynomials
- 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 using fewer random bits
- Matrix multiplication via arithmetic progressions
- Factoring polynomials and primitive elements for special primes
- Univariate polynomial factorization 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}\)
- An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials over GF(p)
- Factoring polynomials with rational coefficients
- Smoothness and factoring polynomials over finite fields
- On fast multiplication of polynomials over arbitrary algebras
- Counting irreducible factors of polynomials over a finite field
- Equations over finite fields. An elementary approach
- 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 multiplication of polynomials over fields of characteristic 2
- Fast rectangular matrix multiplication and applications
- 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
- Deterministic analysis of aleatoric methods of polynomial factorization over finite fields
- Idempotent computation over finite fields
- Algorithmic number theory. 3rd international symposium, ANTS-III, Portland, OR, USA, June 21--25, 1998. Proceedings
- Factoring polynomials over arbitrary finite fields
- Deterministic irreducibility testing of polynomials over large finite fields
- Subspaces and polynomial factorizations over finite fields
- 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 Hensel factorization. I
- On the computational power of pushdown automata
- Fast multiplication of large numbers
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- On the number of irreducible factors of a polynomial over a finite field
- Generalized riemann hypothesis and factoring polynomials over finite fields
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Counting polynomials with a given number of zeros in a finite field
- 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]
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Solving sparse linear equations over finite fields
- Factoring polynomials over finite fields
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- Probabilistic Algorithms in Finite Fields
- On Polynomial Factorization Over Finite Fields
- A New Algorithm for Factoring Polynomials Over Finite Fields
- Subgroup Refinement Algorithms for Root Finding in $GF(q)$
- Galois Groups and Factoring Polynomials over Finite Fields
- A Fast Monte-Carlo Test for Primality
- On the Efficiency of Algorithms for Polynomial Factoring
- Computational Complexity of Probabilistic Turing Machines
- Factoring Polynomials over a Finite Field
- A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(pm) of GF(p), p a Small Prime
- Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases
- On a New Factorization Algorithm for Polynomials Over Finite Fields
- Subquadratic-time factoring of polynomials over finite fields
- Analysis of Ben-Or's polynomial irreducibility test
- A geometric approach to root finding in GT(q/sup m/)
- Un Algorithme De Construction Des Idempotents Primitifs D'Ideaux D'Algebres Sur Fq
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- Distinct Degree Factorizations for Polynomials over a Finite Field
- On Bivariate Polynomial Factorization over Finite Fields
- Factorization of the General Polynomial by Means of Its Homomorphic Congruential Functions
- Hybrid methods for finding roots of a polynomial - With application to BCH decoding (Corresp.)
- Factorization of Polynomials Over Finite Fields
This page was built for publication: Factoring polynomials over finite fields: A survey
