Research Article
An Algorithm to Find the Irreducible Polynomials Over Galois Field GF(pm)
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 109 - Issue 15 |
| Published: January 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 },
year = { 2015 },
volume = { 109 },
number = { 15 },
pages = { 24-29 },
doi = { 10.5120/19266-1012 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%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)%T
%J International Journal of Computer Applications
%V 109
%N 15
%P 24-29
%R 10.5120/19266-1012
%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
- Lidl R. , Niederreiter H. , Finite Fields, Encyclopedia of Mathematics and its Applications, Vol. 20, Addison-Wesley Publishing Company, 1983.
- Church R. , "Tables of Irreducible Polynomials for the first four Prime Moduli", Annals of Mathematics, Vol. 36(1), pp. 198 – 209, January, 1935.
- 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.
- Berlekamp E. R. , "Factoring Polynomial over finite fileds", Bell Syst. Tech. J. , Vol. 46, pp. 1853 – 1859, 1967.
- 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.
- Cantor D. G. , "On Arithmetical Algorithms over Finite Fields" J. Combinatorial Theory Series A 9, pp. 285 – 300 (1989).
- Bach E. and Shoup V. , "Factoring Polynomials using Random Bits", J. Symbolic Computation, Vol 9, pp. 229 – 239, 1990.
- Berlekamp E. R. , "Factoring Polynomial over large finite fileds", Math. Comput. Vol. 24 (11), pp. 713 – 735, 1970.
- Shoup, V. , "New algorithms for finding irreducible polynomials in finite fields", Math. Comput. Vol. 54, pp. 435 – 447, 1990.
- Daemen J. , Rijmen V. , AES Proposal: Rijndael, AES Algorithm Submission, September 3, 1999.
- FIPS Pub. 197, Announcing the Advanced Encryption Standard (AES), November 26, 2001.
- Stinson D. R. , Cryptography Theory and Practice (Boca Raton, Chapman & Hall, CRC, 3rd Edition, 2006).
- Stallings W. , Cryptography and Network Security Principles and Practices, Delhi, Pearson Education, 4th Edition, 2008.
- Forouzan B. A. , Mukhopadhyay D. , Cryptography and Network Security, New Delhi, TMH, 2nd Edition, 2011.
- Hasan M. A. , "Double-Basis Multiplicative Inversion Over GF(2m)", IEEE Trans. Comp. , Vol. 47,(9), pp. 960 – 970, 1998.
- Arguello F. , "Lehmer-based algorithm for computing inverses in Galois fields GF(2m)", Electronics Letters, Vol. 42(5), 2006.
- 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.
- https://www. academia. edu/attachments/34220711/download_file
Index Terms
Keywords