CFP last date
20 March 2024
Reseach Article

An Algorithm to Find the Irreducible Polynomials Over Galois Field GF(pm)

by J K M Sadique Uz Zaman, Sankhanil Dey, Ranjan Ghosh
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 109 - Number 15
Year of Publication: 2015
Authors: J K M Sadique Uz Zaman, Sankhanil Dey, Ranjan Ghosh
10.5120/19266-1012

J K M Sadique Uz Zaman, Sankhanil Dey, Ranjan Ghosh . An Algorithm to Find the Irreducible Polynomials Over Galois Field GF(pm). International Journal of Computer Applications. 109, 15 ( January 2015), 24-29. DOI=10.5120/19266-1012

@article{ 10.5120/19266-1012,
author = { J K M Sadique Uz Zaman, Sankhanil Dey, Ranjan Ghosh },
title = { An Algorithm to Find the Irreducible Polynomials Over Galois Field GF(pm) },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 109 },
number = { 15 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 24-29 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume109/number15/19266-1012/ },
doi = { 10.5120/19266-1012 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:44:53.948034+05:30
%A J K M Sadique Uz Zaman
%A Sankhanil Dey
%A Ranjan Ghosh
%T An Algorithm to Find the Irreducible Polynomials Over Galois Field GF(pm)
%J International Journal of Computer Applications
%@ 0975-8887
%V 109
%N 15
%P 24-29
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Irreducible Polynomials over GF(pm) and the multiplicative inverses under it are important in cryptography. Presently the method of deriving irreducible polynomials of a particular prime modulus is very primitive and time consuming. In this paper, in order to find all irreducible polynomials, be it monic or non-monic, of all prime moduli p with all its order m, a fast deterministic computer algorithm based on an algebraic method producing a (m×m) matrix is proposed. The maximum number of terms in each column of the matrix is 2j where j is the column index.

References
  1. Lidl R. , Niederreiter H. , Finite Fields, Encyclopedia of Mathematics and its Applications, Vol. 20, Addison-Wesley Publishing Company, 1983.
  2. Church R. , "Tables of Irreducible Polynomials for the first four Prime Moduli", Annals of Mathematics, Vol. 36(1), pp. 198 – 209, January, 1935.
  3. Chebolu S. K. and Minac. J. , "Counting Irreducible Polynomials over Finite Fields Using the Inclusion-Exclusion Principle", Math. Mag. , Vol. 84(5), pp. 369 – 371, 2011.
  4. Berlekamp E. R. , "Factoring Polynomial over finite fileds", Bell Syst. Tech. J. , Vol. 46, pp. 1853 – 1859, 1967.
  5. Adleman L. M. and Lenstra H. W. , "Finding irreducible polynomials over finite fields", Proc. 18th ACM Conf. on The Theory of Computing, Berkeley, CA, pp. 350 – 355. , 1986.
  6. Cantor D. G. , "On Arithmetical Algorithms over Finite Fields" J. Combinatorial Theory Series A 9, pp. 285 – 300 (1989).
  7. Bach E. and Shoup V. , "Factoring Polynomials using Random Bits", J. Symbolic Computation, Vol 9, pp. 229 – 239, 1990.
  8. Berlekamp E. R. , "Factoring Polynomial over large finite fileds", Math. Comput. Vol. 24 (11), pp. 713 – 735, 1970.
  9. Shoup, V. , "New algorithms for finding irreducible polynomials in finite fields", Math. Comput. Vol. 54, pp. 435 – 447, 1990.
  10. Daemen J. , Rijmen V. , AES Proposal: Rijndael, AES Algorithm Submission, September 3, 1999.
  11. FIPS Pub. 197, Announcing the Advanced Encryption Standard (AES), November 26, 2001.
  12. Stinson D. R. , Cryptography Theory and Practice (Boca Raton, Chapman & Hall, CRC, 3rd Edition, 2006).
  13. Stallings W. , Cryptography and Network Security Principles and Practices, Delhi, Pearson Education, 4th Edition, 2008.
  14. Forouzan B. A. , Mukhopadhyay D. , Cryptography and Network Security, New Delhi, TMH, 2nd Edition, 2011.
  15. Hasan M. A. , "Double-Basis Multiplicative Inversion Over GF(2m)", IEEE Trans. Comp. , Vol. 47,(9), pp. 960 – 970, 1998.
  16. Arguello F. , "Lehmer-based algorithm for computing inverses in Galois fields GF(2m)", Electronics Letters, Vol. 42(5), 2006.
  17. Zaman JKM. S. and Ghosh R. , "Multiplicative Polynomial Inverse over GF(73): Crisis of EEA and its Solution", Applied Computation and Security Systems, Advances in Intelligent Systems and Computing, Volume 305, pp. 87 – 107, DOI: 10. 1007/978-81-322-1988-0_6.
  18. https://www. academia. edu/attachments/34220711/download_file
Index Terms

Computer Science
Information Sciences

Keywords

Extended Finite field Finite field Galois field GF(73) Irreducible polynomial Multiplicative inverse.