Composite Algorithm The New Algorithm to Search for Monic Irreducible Polynomials over Extended Galois Fields

Sankhanil Dey; Amlan Chakrabarti; Ranjan Ghosh

Paper 2020/360

Composite Algorithm The New Algorithm to Search for Monic Irreducible Polynomials over Extended Galois Fields

Sankhanil Dey, Amlan Chakrabarti, and Ranjan Ghosh

Abstract

Irreducible polynomials or IPs have many applications in the field of computer science and information technology. Algorithms in artificial intelligence and substitution boxes in cryptographic ciphers are some evident example of such important applications. But till now the study is mostly limited to the binary Galois field GF prime two and extension q . Some works are there to generate IPs over some non-binary Galois field GF prime p and extension q where p is the prime modulus and p greater than two but the maximum value of p is not more than thirteen and the maximum value of extension q is not more than four. In this paper a new algorithm to search for monic irreducible polynomials over extended Galois field GF prime p and extension q entitled as Composite Algorithm is introduced to computer scientists. Here all possible set of two monic elemental polynomials or EPs one one with highest degree less than equal to q minus one divided by two (for odd value of q) and less than equal to q divided by two (for even value of q) is multiplied over the Galois field GF prime p and extension q to one with highest degree greater than equal to q minus one divided by two (for odd value of q) and greater than q divided by two (for even value of q). All resultant monic polynomials are then divided over the Galois field GF prime p and extension q by a monic basic polynomial or BP one. If for all resultant polynomials the residue is one for a monic BP then the monic BP is termed as monic IP. The time complexity of the said algorithm is prove to be the best among existing such algorithms and efficient of all among them.

Note: The study is the stepping stone of the generation of 4 bit, 8 bit and 32 bit S-boxes using irreducible polynomials over extended Galois field with large values of primes and extensions. The study is in review in SADHANA, Academy Proceedings in Engineering Sciences, Indian Academy of science, Springer India.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Polynomials Irreducible Polynomials Algorithms Numerical Algorithms Discrete Mathematics in Cryptology Cryptography
Contact author(s): sdrpe_rs @ caluniv ac in
History: 2020-03-28: received
Short URL: https://ia.cr/2020/360
License: CC BY

BibTeX

@misc{cryptoeprint:2020/360,
      author = {Sankhanil Dey and Amlan Chakrabarti and Ranjan Ghosh},
      title = {Composite Algorithm The New Algorithm to Search for Monic Irreducible Polynomials over Extended Galois Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2020/360},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/360}},
      url = {https://eprint.iacr.org/2020/360}
}