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 ,  use the Berlekamp-Massey algorithm  and they have a complexity O(m2). We reach mis improvement taking into account a systolic implementation  of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm. © 1995 Springer-Verlag New York Inc.
|Journal||Mathematical Systems Theory|
|Publication status||Published - 1 Jan 1995|