Portal de Periódicos da CAPES

Factoring polynomials and primitive elements for special primes

1987; Elsevier BV; Volume: 52; Issue: 1-2 Linguagem: Inglês

10.1016/0304-3975(87)90081-8

1879-2294

Joachim von zur Gathen,

Cryptography and Residue Arithmetic

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.