Factoring polynomials and primitive elements for special primes
type: Item
instance of: scholarly article
title: Factoring polynomials and primitive elements for special primes
zbMATH Open document ID: 0633.12009
DOI: 10.1016/0304-3975(87)90081-8
author: Joachim von zur Gathen
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: For those prime numbers \(p\), for which all prime factors of \(p-1\) are small, the two problems of finding a primitive element modulo \(p\) and of factoring univariate polynomials over finite fields of characteristic \(p\) are (deterministically) polynomial-time equivalent. Assuming the Extended Riemann Hypothesis, they can be solved in polynomial time.
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12-04
zbMATH DE Number: 4029708
zbMATH Keywords: factoring univariate polynomials over finite fields
zbMATH Keywords: polynomial time
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90081-8
OpenAlex ID: W2138459436
cites work: The least quadratic non residue
cites work: Q5550483
cites work: Factoring Polynomials Over Large Finite Fields
cites work: ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
cites work: A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
cites work: A New Algorithm for Factoring Polynomials Over Finite Fields
cites work: Q4747509
cites work: Parallel Algorithms for Algebraic Problems
cites work: Q4724729
cites work: Q4725742
cites work: Factorization of Multivariate Polynomials Over Finite Fields
cites work: On Polynomial Factorization Over Finite Fields
cites work: On the number of positive integers \(\leq x\) and free of prime factors \(>y\)
cites work: Q5585020
cites work: Factoring multivariate polynomials over finite fields
cites work: Factoring polynomials with rational coefficients
cites work: On the Efficiency of Algorithms for Polynomial Factoring
cites work: Numbers with small prime factors, and the least 𝑘th power non-residue
cites work: Probabilistic Algorithms in Finite Fields
cites work: Fast multiplication of polynomials over fields of characteristic 2
cites work: Fast multiplication of large numbers
cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
cites work: Q3286403
description: scientific article; zbMATH DE number 4029708