A fast algorithm to compute irreducible and primitive polynomials in finite fields

    Research output: Contribution to journalArticleResearchpeer-review

    5 Citations (Scopus)

    Abstract

    In this paper we present a method to compute all the irreducible and primitive polynomials of degree m over the finite field GF(q). Our method finds each new irreducible or primitive polynomial with a complexity of O(m) arithmetic operations in GF(q). The best previously known methods [3], [10] use the Berlekamp-Massey algorithm [7] and they have a complexity O(m2). We reach mis improvement taking into account a systolic implementation [2] of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm. © 1995 Springer-Verlag New York Inc.
    Original languageEnglish
    Pages (from-to)13-20
    JournalMathematical Systems Theory
    Volume28
    Issue number1
    DOIs
    Publication statusPublished - 1 Jan 1995

    Fingerprint

    Dive into the research topics of 'A fast algorithm to compute irreducible and primitive polynomials in finite fields'. Together they form a unique fingerprint.

    Cite this