Fast construction of irreducible polynomials over finite fields

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

Abstract

An algorithm is presented that constructs an irreducible polynomial of specified degree n over a finite field Fq. The algorithm is probabilistic, and is asymptotically faster than previously known probabilistic algorithms for this problem. It uses an expected number of Oqq(n2+n log q) operations in Fq, where the `soft-O' Oqq indicates an implicit factor of (log n)O(1).

Original languageEnglish (US)
Title of host publicationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages484-492
Number of pages9
StatePublished - 1993
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Fast construction of irreducible polynomials over finite fields'. Together they form a unique fingerprint.

  • Cite this

    Shoup, V. (1993). Fast construction of irreducible polynomials over finite fields. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 484-492). Publ by ACM.