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
    0 references
    0 references
    0 references
    0 references
    factoring univariate polynomials over finite fields
    0 references
    polynomial time
    0 references
    0 references