Factoring polynomials and primitive elements for special primes (Q1095971)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Factoring polynomials and primitive elements for special primes |
scientific article; zbMATH DE number 4029708
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Factoring polynomials and primitive elements for special primes |
scientific article; zbMATH DE number 4029708 |
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
