Factoring polynomials and primitive elements for special primes

DOI10.1016/0304-3975(87)90081-8zbMath0633.12009OpenAlexW2138459436MaRDI QIDQ1095971

Joachim von zur Gathen

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90081-8

zbMATH Keywords

polynomial timefactoring univariate polynomials over finite fields

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items

Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝, Computing Frobenius maps and factoring polynomials, Deterministic root finding over finite fields using Graeffe transforms, Univariate polynomial factorization over finite fields, Factoring polynomials modulo special primes, On the deterministic complexity of factoring polynomials over finite fields, Constructing nonresidues in finite fields and the extended Riemann hypothesis, Smoothness and factoring polynomials over finite fields, Computational problems in the theory of finite fields, Factoring polynomials over special finite fields, Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes, Factoring polynomials over finite fields: A survey, On the deterministic complexity of factoring polynomials, Searching for Primitive Roots in Finite Fields, Deterministic polynomial factoring and association schemes, Unnamed Item, Deterministic irreducibility testing of polynomials over large finite fields, Trading GRH for algebra: Algorithms for factoring polynomials and related structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of positive integers \(\leq x\) and free of prime factors \(>y\)
• Factoring multivariate polynomials over finite fields
• Factoring polynomials with rational coefficients
• Fast multiplication of polynomials over fields of characteristic 2
• Fast multiplication of large numbers
• The least quadratic non residue
• Parallel Algorithms for Algebraic Problems
• A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Factorization of Multivariate Polynomials Over Finite Fields
• Probabilistic Algorithms in Finite Fields
• On Polynomial Factorization Over Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• On the Efficiency of Algorithms for Polynomial Factoring
• Numbers with small prime factors, and the least 𝑘th power non-residue
• Factoring Polynomials Over Large Finite Fields
• ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD