Substitution boxes or S-boxes play a significant role in encryption and de-cryption of bit level plaintext and cipher-text respectively. Irreducible Poly-nomials (IPs) have been used to construct 4-bit or 8-bit substitution boxes in many cryptographic block ciphers. In Advance Encryption Standard, the ele-ments of 8-bit S-box have been obtained from the Multiplicative Inverse (MI) of elemental polynomials (EPs) of the 1st IP over Galois field GF(28) by adding an additive element. In this paper, a mathematical method and the algorithm of the said method with the discussion of the execution time of the algorithm, to obtain monic IPs over Galois field GF(pq) have been illustrated with example. The method is very similar to polynomial multiplication of two polynomials over Galois field GF(pq) but has a difference in execution. The decimal equivalents of polynomials have been used to identify Basic Polynomials (BPs), EPs, IPs and Reducible polynomials (RPs). The monic RPs have been determined by this method and have been cancelled out to produce monic IPs. The non-monic IPs have been obtained with multiplication of α where？α∈ GF(pq)？and assume values from 2 to (p −1) to monic IPs.
References
[1]
Adams, C. and Tavares, S. (1990) The Structured Design of Cryptographically Good S-Boxes. Journal of Cryptology, 3, 27-41.
[2]
Feistel, H. (1971) Block Cipher Cryptographic System. US Patent 3798359.
[3]
Data Encryption Standard, Federal Information Processing Standards Publication (FIPS PUB) 46, National Bureau of Standards, Washington, DC (1977).
[4]
Data Encryption Standard (DES), Federal Information Processing Standards Publication (FIPS PUB) 46-3, National Institute of Standards and Technology, Gaithersburg, MD (1999).
[5]
Daemen, J. and Rijmen, V. (2000) AES Proposal: Rijndael. https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-%20guidelines/documents/aes-development/rijndael-ammended.pdf
[6]
Vaudenay, S. and Moriai, S. (1994) Comparison of the Randomness Provided by Some AES Candidates, EUROCRYPT 1994. Springer Verlag, No. 950, 386-397.
Church, R. (1935) Tables of Irreducible Polynomials for the First Four Prime Moduli. Annals of Mathematics, Second Series, 36, 198-209. http://www.jstor.org/stable/1968675.
[10]
Swan, R.G. (1962) Factorization of Polynomials over Finite Fields. Pacific Journal of Mathematics, 12, 1099-1106. https://projecteuclid.org/euclid.pjm/1103036322.
[11]
Bartee, T.C. and Schneider, D.I. (1963) Computation with Finite Fields. Information and Control, 6, 79-98.
[12]
Berlekamp, E.R. (1967) Factoring Polynomials over Finite Fields. Bell System Technical Journal, 46, 1853-1859.
[13]
Kasami, T., Lin, S. and Peterson, W. (1968) Polynomial Codes. IEEE Transactions on Information Theory, 14, 807-814.
[14]
Berlekamp, E.R. (1970) Factoring Polynomials over Large Finite Fields. Mathematics of Computation, 24, 713-735. https://doi.org/10.1090/S0025-5718-1970-0276200-X
[15]
Rabin, M.O. (1980) Probabilistic Algorithms in Finite Fields. SIAM Journal on Computing, 9, 273-280. https://doi.org/10.1137/0209024
[16]
Lenstra, A.K. (1985) Factoring Multivariate Polynomials over Finite Fields. Journal of Computer and System Sciences, 30, 235-248. https://doi.org/10.1016/0022-0000(85)90016-9
[17]
McEliece, R.J. (1987) Factoring Polynomials over Finite Fields. In: McEliece, R.J., Ed., Finite Fields for Computer Scientists and Engineers, Springer, Berlin, 75-96.
[18]
Rónyai, L. (1988) Factoring Polynomials over Finite Fields. Journal of Algorithms, 9, 391-400. https://doi.org/10.1016/0196-6774(88)90029-6
[19]
Wan, D.Q. (1990) Factoring Multivariate Polynomials over Large Finite Fields. Mathematics of Computation, 54, 755-770. https://doi.org/10.1090/S0025-5718-1990-1011448-0
[20]
Rybowicz, M. (1990) Search of Primitive Polynomials over Finite Fields. Journal of Pure and Applied Algebra, 65, 139-151. https://doi.org/10.1016/0022-4049(90)90115-X
[21]
Shoup, V. (1990) New Algorithms for Finding Irreducible Polynomials over Finite Fields. Mathematics of Computation, 54, 435-447.
[22]
Rónyai, L. (1992) Galois Groups and Factoring Polynomials over Finite Fields. SIAM Journal on Discrete Mathematics, 5, 345-365. https://doi.org/10.1137/0405026
[23]
Zivkovic, M. (1994) Table of Primitive Binary Polynomials. Mathematics of Computation, 63, 301-306. https://doi.org/10.2307/2153576
[24]
Shparlinski, I. (1996) On Finding Primitive Roots in Finite Fields. Theoretical Computer Science, 157, 273-275. https://doi.org/10.1016/0304-3975(95)00164-6
[25]
Flajolet, P., Gourdon, X. and Panario, D. (1996) Random Polynomials and Polynomial Factorization. Lecture Notes in Computer Science, Vol. 1099, Springer-Verlag, New York/Berlin, 232-243.
[26]
Gao, S. and Panario, D. (1997) Tests and Constructions of Irreducible Polynomials over Finite Fields. In: Cucker, F. and Shub, M., Eds., Foundations of Computational Mathematics, Springer, Berlin, Heidelberg, 346-361. https://doi.org/10.1007/978-3-642-60539-0_27
[27]
Kaltofen, E. and Shoup, V. (1998) Subquadratic-Time Factoring of Polynomials over Finite Fields. Mathematics of Computation of the American Mathematical Society, 67, 1179-1197. https://doi.org/10.1090/S0025-5718-98-00944-2
[28]
Bach, E., von zur Gathen, J. and Lenstra Jr., H.W. (2001) Factoring Polynomials over Special Finite Fields. Finite Fields and Their Applications, 7, 5-28. https://doi.org/10.1006/ffta.2000.0306
[29]
Gao, S. and Lauder, A.G.B. (2002) Hensel Lifting and Bivariate Polynomial Factorisation over Finite Fields. Mathematics of Computation, 71, 1663-1676. https://doi.org/10.1090/S0025-5718-01-01393-X
[30]
Brent, R.P. and Zimmermann, P. (2003) Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials. In: Van Der Poorten, A., Van Der Poorten, A.J., Stein, A. and Williams, H.C., Eds., High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, American Mathematical Society, Providence, 91-102.
[31]
Saxena, N.R. and McCluskey, E.J. (2004) Primitive Polynomial Generation Algorithms Implementation and Performance Analysis. Technical Report (CRC TR 04-03), Center for Reliable Computing.
[32]
Gao, S., Kaltofen, E. and Lauder, A.G.B. (2004) Deterministic Distinct-Degree Factorization of Polynomials over Finite Fields. Journal of Symbolic Computation, 38, 1461-1470. https://doi.org/10.1016/j.jsc.2004.05.004
[33]
Maitraa, S., Gupta, K.C. and Venkateswar, A. (2005) Results on Multiples of Primitive Polynomials and Their Products over GF(2). Theoretical Computer Science, 341, 311-343. https://doi.org/10.1016/j.tcs.2005.04.011
[34]
Scott, M. (2007) Optimal Irreducible Polynomials for GF(2m) Arithmetic. Dublin City University, Dublin.
[35]
Fernandez, C.K. (2008) Pascal Polynomials over GF(2). Master’s Thesis, Naval Postgraduate School Monterey CA Dept. of Mathematics, Accession No. ADA483773.
[36]
Saha, C. (2008) A Note on Irreducible Polynomials and Identity Testing.
[37]
Ahmed, A. and Lbekkouri, A. (2009) Determination of Irreducible and Primitive Polynomials over a Binary Finite Field. Conference: Workshop sur les Technologies de l’Information et de la Communication, Agadir, 24-25 Décembre 2009, 94.
[38]
Richards, C. (2009) Algorithms for Factoring Square-Free Polynomials over Finite Fields.
[39]
Kim, R. and Koepf, W. (2009) Divisibility of Trinomials by Irreducible Polynomials over F2. International Journal of Algebra, 3, 189-197.
[40]
Hanif, S. and Imran, M. (2011) Factorization Algorithms for Polynomials over Finite Fields. Degree Project, School of Computer Science, Physics and Mathematics, Linnaeus University.
[41]
Wang, L. and Wang, Q. (2012) On Explicit Factors of Cyclotomic Polynomials over Finite Fields. Designs, Codes and Cryptography, 63, 87-104. https://doi.org/10.1007/s10623-011-9537-6
[42]
Couveignes, J.M. and Lercier, R. (2013) Fast Construction of Irreducible Polynomials over Finite Fields. Israel Journal of Mathematics, 194, 77-105. https://doi.org/10.1007/s11856-012-0070-8
[43]
Marquis, D. (2014) Deterministic Factorization of Polynomials over Finite Fields. Thesis: MS in Pur Mathematics, Carleton University, Ottawa.
[44]
Hammarhjelm, G. (2014) Construction of Irreducible Polynomials over Finite Fields. UUDM Project Report 17, Uppasala Universitet, Uppasala.
[45]
Cavanna, N. (2014) Polynomial Factoring Algorithms and Their Computational Complexity. Honors Scholar Theses, 384. http://digitalcommons.uconn.edu/srhonors_theses/384
[46]
Wang, J. and Dong, Z. (2014) Simple Method to Find Primitive Polynomials of Degree n over GF(2) Where 2n−1 Is a Mersenne Prime. http://worldcomp-proceedings.com/proc/p2014/SAM9773.pdf
[47]
Sadique Uz Zaman, J.K.M., Dey, S. and Ghosh, R. (2015) An Algorithm to Find the Irreducible Polynomials over Galois Field GF(pm). International Journal of Computer Applications, 109, 24-29.
[48]
Ha, J. (2016) Irreducible Polynomials with Several Prescribed Coefficients. Finite Fields and Their Applications, 40, 10-25. https://doi.org/10.1016/j.ffa.2016.02.006
[49]
Poonen, B. (2017) Using Zeta Functions to Factor Polynomials over Finite Fields.
[50]
Weisstein, E.W. (2004) Integer Polynomial. From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/IntegerPolynomial.html
