Improved Trial Division Technique for Primality Checking in RSA Algorithm
Kumarjit Banerjee, Satyendra Nath Mandal, Sanjoy Kumar Das · International Journal of Computer Network and Information Security · 2013
The RSA cryptosystem, invented by Ron Rivest, Adi Shamir and Len Adleman was first publicized in the August 1977 issue of Scientific A merican.The security level of this algorith m very much depends on two large prime nu mbers.To check the primality of large number in personal co mputer is huge time consuming using the best known trial d ivision algorith m.The t ime complexity for primality testing has been reduced using the representation of divisors in the form o f 6n±1.According to the fundamental theorem o f Arith metic, every number has unique factorization.So to check primality, it is sufficient to check if the nu mber is divisible by any prime below the square root of the number.The set of divisors obtained by 6n±1 form representation contains many co mposites.These composite numbers have been reduced by 30k approach.In this paper, the number of co mposites has been further reduced using 210k approach.A performance analysis in time co mplexity has been given between 210k approach and other prior applied methods.It has been observed that the time co mp lexity for primality testing has been reduced using 210k approach.