Factoring polynomials and primitive elements for special primes
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.
factoring univariate polynomials over finite fields
scientific article; zbMATH DE number 4029708
scientific article