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 polynomialscryptologyS-boxesAlgorithms
Contact author(s)
sdrpe_rs @ caluniv ac in
History
2020-04-02: received
Short URL
https://ia.cr/2020/365
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.