Smoothness and factoring polynomials over finite fields
The author proves the following theorem: There is a deterministic algorithm for factoring polynomials over \(\mathbb{F}_ p\) (\(p\) prime), which on polynomials over \(\mathbb{F}_ p\) of degree \(n\) is running in time \([S(p-1)]^{1/2}[n\log p]^{O(1)}\), under the assumption of the Extended Riemann Hypothesis (ERH). Here \(S(m)\) is the largest prime divisor of \(m\). The algorithm refines algorithms due to \textit{J. von zur Gathen} [Theor. Comput. Sci. 52, 77-89 (1987; Zbl 0633.12009)] and \textit{L. Rónyai} [Combinatorica 9, 199-206 (1989; Zbl 0694.68039)] which required running time \(S(p-1)[n\log p]^{O(1)}\). If ERH indeed holds, then the proposed algorithm is more efficient than the currently best- known for factoring arbitrary polynomials over \(\mathbb{F}_ p\).
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Factoring polynomials and primitive elements for special primes
- Factoring polynomials modulo special primes
- Factoring Polynomials Over Large Finite Fields
- scientific article; zbMATH DE number 3882549 (Why is no real title available?)
- scientific article; zbMATH DE number 4152517 (Why is no real title available?)
- scientific article; zbMATH DE number 3460351 (Why is no real title available?)
- scientific article; zbMATH DE number 4123827 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- On fast multiplication of polynomials over arbitrary algebras
- On the deterministic complexity of factoring polynomials over finite fields
- Some results on computational complexity
- The average of the least primitive root
- The least quadratic non residue
- Univariate polynomial factorization 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\)
- Efficiently factoring polynomials modulo \(p^4\)
- Smoothness testing of polynomials over finite fields
- Deterministic root finding over finite fields using Graeffe transforms
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- Using partial smoothness of p-1 for factoring polynomials modulo p
- Generalized riemann hypothesis and factoring polynomials over finite fields
- Searching for Primitive Roots in Finite Fields
- Constructing nonresidues in finite fields and the extended Riemann hypothesis
- Factoring polynomials over finite fields using balance test
- Square-free smooth polynomials in residue classes and generators of irreducible polynomials
- scientific article; zbMATH DE number 7559413 (Why is no real title available?)
- A generalized successive resultants algorithm
- On Bivariate Polynomial Factorization over Finite Fields
- SMOOTHNESS IN PENCILS OF HYPERSURFACES OVER FINITE FIELDS
- Factoring polynomials over finite fields: A survey
- On the deterministic complexity of factoring polynomials
This page was built for publication: Smoothness and factoring polynomials over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178194)
