Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



New algorithms for finding irreducible polynomials over finite fields

Author: Victor Shoup
Journal: Math. Comp. 54 (1990), 435-447
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 993933
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new algorithm for finding an irreducible polynomial of specified degree over a finite field. Our algorithm is deterministic, and it runs in polynomial time for fields of small characteristic. We in fact prove the stronger result that the problem of finding irreducible polynomials of specified degree over a finite field is deterministic polynomial-time reducible to the problem of factoring polynomials over the prime field.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11Y16

Retrieve articles in all journals with MSC: 11T06, 11Y16

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society