Portal de Periódicos da CAPES

Irreducible polynomials over finite fields

1986; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-17179-7_15

1611-3349

Joachim von zur Gathen,

Cryptography and Residue Arithmetic

Several methods of computing irreducible polynomials over finite fields are presented. If preprocessing, depending only on p , is allowed for free, then an irreducible polynomial of degree at least n over Z p can be computed deterministically with O(n logp), i.e. O(output size), bit operations. The estimates for the preprocessing time depend on unproven conjectures.