  Irreducible polynomials play an important role till now, in construction of
8-bit S-Boxes in ciphers. The 8-bit S-Box of Advanced Encryption Standard is a
list of decimal equivalents of Multiplicative Inverses (MI) of all the
elemental polynomials of a monic irreducible polynomial over Galois Field
GF(2^8) [1]. In this paper a new method to search monic Irreducible Polynomials
(IPs) over Galois fields GF(p^q) has been introduced. Here the decimal
equivalents of each monic elemental polynomial (ep), two at a time, are split
into the p-nary coefficients of each term, of those two monic elemental
polynomials. From those coefficients the p-nary coefficients of the resultant
monic basic polynomials (BP) have been obtained. The decimal equivalents of
resultant basic polynomials with p-nary coefficients are treated as decimal
equivalents of the monic reducible polynomials, since monic reducible
polynomials must have two monic elemental polynomials as its factor. The
decimal equivalents of polynomials belonging to the list of reducible
polynomials are cancelled leaving behind the monic irreducible polynomials. A
non-monic irreducible polynomial is computed by multiplying a monic irreducible
polynomial by alpha where alpha belongs to GF(p^q) and assumes values from 2 to
(p-1).
