New algorithms for finding irreducible polynomials over finite fields

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An algorithm is presented for finding an irreducible polynomial of specified degree over a finite field. It is deterministic and runs in polynomial time for fields of small characteristics. A proof is given of the stronger result, that the problem of finding irreducible polynomials of specified degree over a finite field K is deterministic-polynomial-time reducible to the problem of factoring polynomials over the prime field of K.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages283-290
Number of pages8
ISBN (Print)0818608773, 9780818608773
DOIs
StatePublished - 1988

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'New algorithms for finding irreducible polynomials over finite fields'. Together they form a unique fingerprint.

  • Cite this

    Shoup, V. (1988). New algorithms for finding irreducible polynomials over finite fields. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 283-290). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21944