Factoring polynomials and primitive elements for special primes (Q1095971)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Factoring polynomials and primitive elements for special primes |
scientific article |
Statements
Factoring polynomials and primitive elements for special primes (English)
0 references
1987
0 references
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.
0 references
factoring univariate polynomials over finite fields
0 references
polynomial time
0 references