We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
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
journal cover thumbnail

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.

Powered by PhDFocusTM