International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 5, No. 9, 8 Jul. 2013
Cover page and Table of Contents: PDF (size: 163KB)
Improved Trial Division Technique for Primality Checking in RSA Algorithm
Full Text (PDF, 163KB), PP.51-57
Views: 0 Downloads: 0
Author(s)
Kumarjit Banerjee
1,*
Satyendra Nath Mandal
1
Sanjoy Kumar Das
2
Index Terms
Improved Trial Division, RSA Algorithm, Primality Checking, Pseudo primes, 210k Approach
Abstract
The RSA cryptosystem, invented by Ron Rivest, Adi Shamir and Len Adleman was first publicized in the August 1977 issue of Scientific American. The security level of this algorithm very much depends on two large prime numbers. To check the primality of large number in personal computer is huge time consuming using the best known trial division algorithm. The time complexity for primality testing has been reduced using the representation of divisors in the form of 6n±1. According to the fundamental theorem of Arithmetic, every number has unique factorization. So to check primality, it is sufficient to check if the number is divisible by any prime below the square root of the number. The set of divisors obtained by 6n±1 form representation contains many composites. These composite numbers have been reduced by 30k approach. In this paper, the number of composites has been further reduced using 210k approach. A performance analysis in time complexity has been given between 210k approach and other prior applied methods. It has been observed that the time complexity for primality testing has been reduced using 210k approach.
Cite This Paper
Kumarjit Banerjee, Satyendra Nath Mandal, Sanjoy Kumar Das, "Improved Trial Division Technique for Primality Checking in RSA Algorithm", International Journal of Computer Network and Information Security(IJCNIS), vol.5, no.9, pp.51-57,2013. DOI:10.5815/ijcnis.2013.09.07
Reference
[1]Ron L. Rivest, Adi Shamir, and Len Adleman, "A method for obtaining digital Signatures and public-key cryptosystems", Communications of the ACM 21 (1978), pp 120-126.
[2]Boneh and Durfee, "Cryptanalysis of RSA with private key d less than n0.292", IEEETIT: IEEE Transactions on Information Theory, Volume 46, Issue 4, Jul 2000 pp. 1339 – 1349.
[3]C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25•109", Math. Comp., 35:151 (1980) pp. 1003–1026.
[4]Mandal N. Satyendra, Banerjee Kumarjit, Maiti Biswajit, Palchaudhury J. , "Modified Trail division for Implementation of RSA Algorithm with Large Integers", Int. Journal Advanced Networking and Applications Volume: 01, Issue: 04, Pages: 210-216 (2009).
[5]Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory, Volume 12 Issue no. 1, pp. 128–138 (1980).
[6]M. Wiener, "Cryptanalysis of short rsa secret exponents", IEEE Transactions on Information Theory 36 (1990), pp.553-558.
[7]Banerjee Kumarjit, Mandal N. Satyendra, Palchaudhury J, Banerjee Abhishek, "A Deterministic Approach in Trial Division with Pseusdoprimes for RSA Implementation with Large Numbers", IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.5, No.1, January 2011.
[8]Guicheng Shen, Bingwu Liu, Xuefeng Zheng, "Research on Fast Implementation of RSA with Java", Nanchang, P. R. China, May 22-24, 2009, pp. 186-189.
[9]Banerjee Kumarjit, Mandal Satyendra Nath, Das Sanjoy Kumar, "A Comparative Study of Different Techniques for Prime Testing in Implementation of RSA", ISSN No. 2229-6611, IEMCON 2012, Vol. 2, No. 2, pp 42-47.
[10]David M. Burton, "Elementary Number Theory (2nd ed)", pp 175-181, Universal Books Stall, New Delhi, (2004).
[11]Whitfield Diffie and Martin E. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory IT-22, no. 6, 1976, pp644-654.
[12]Tatsuaki Okamoto and Shigenori Uchiyama, "A new public key cryptosystem as secure as factoring", Lecture notes in Computer Science 1403 (1998), 308-318. MR 1 729 059.
[13]The Prime Pages-prime number research, records and resources, available at http://primes.utm.edu/howmany.shtml last accessed 12.09.2012.
[14]Richard Crandall and Carl Pomerance, "Prime Numbers A Computational (Second Edition)", pp. 83-113 and pp 173-179 and pp 225-227,Springer ISBN-10: 0-387-25282-7,New York(2005).
[15]Song. Y Yan, "Cryptanalytic Attacks on RSA",pp 55-93 and pp 149-187,Springer ISBN-13: 978-0-387-48741-0,New York (2008).
[16]Hinek M. Jason, "Cryptanalysis of RSA and Its Variants", pp 8-10 and pp 17-23, CRC Press, New York (2010).
[17]Mollin A. Richard, "RSA and Public-Key Cryptography", pp 53-108, CRC Press LLC, New York (2003).
[18]Mandal N. Satyendra, Banerjee Kumarjit, Palchaudhury J., Implementation of RSA Algorithm with variable n-padding technique and Miller-Rabin test for Auto-generated Large keys from System Date, Proceedings of the 5th National Conference; INDIACom-2011.