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

Sankhanil Dey; Amlan Chakrabarti; Ranjan Ghosh

Paper 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, 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.

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. Security and Privacy, Wiley Periodicals Inc.
DOI: 10.1002/spy2.110
Keywords: Irreducible polynomials cryptology S-boxes Algorithms
Contact author(s): sdrpe_rs @ caluniv ac in
History: 2020-04-02: received
Short URL: https://ia.cr/2020/365
License: CC BY

BibTeX

@misc{cryptoeprint:2020/365,
      author = {Sankhanil Dey and Amlan Chakrabarti and Ranjan Ghosh},
      title = {A New Algorithm to Find Monic Irreducible Polynomials over Extended Galois field GF prime p and extension q using Positional Arithmetic},
      howpublished = {Cryptology ePrint Archive, Paper 2020/365},
      year = {2020},
      doi = {10.1002/spy2.110},
      note = {\url{https://eprint.iacr.org/2020/365}},
      url = {https://eprint.iacr.org/2020/365}
}