Cryptology ePrint Archive: Report 2020/365

A New Algorithm to Find Monic Irreducible Polynomials over Extended Galois field GF prime p and extension q using Positional Arithmetic

Sankhanil Dey and Amlan Chakrabarti and Ranjan Ghosh

Abstract: Search for monic irreducible polynomials (IPs) over extended Galois field GF(p^q) for a large value of the prime moduli p and a large extension to the Galois Field q is a well needed solution in the field of cryptography. In this paper a new algorithm to obtain monic IPs over extended Galois field GF(p^q) for the large values of p and q is introduced. Here in this paper the positional arithmetic is used to multiply all possible two monic elemental polynomials (EPs) with their Galois field number (GFN) to generate all the monic reducible polynomials (RPs). All the monic RPs are cancelled out from the list of monic basic polynomials (BPs) leaving behind all the monic IPs. Time complexity analysis of the said algorithm is also executed that ensures the algorithm to be less time consuming.

Category / Keywords: foundations / Irreducible polynomials, cryptology, S-boxes, Algorithms

Original Publication (with minor differences): Security and Privacy, Wiley Periodicals Inc.

Date: received 28 Mar 2020

Contact author: sdrpe_rs at caluniv ac in

Available format(s): PDF | BibTeX Citation

Note: This work is devoted to generate irreducible polynomials over the extended Galois fields for large values of prime and extension. This will accelerate the generation of 4-bit, 8-bit, 32-bit S-boxes for block ciphers.

Version: 20200402:122315 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]