Factoring polynomials and primitive elements for special primes (Q1095971)

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.