Performance analysis of index calculus method

Abstract

The security assumption for the cryptosystems based on the Discrete logarithm problem (DLP) is one way function, i.e., an attacker cannot recover the discrete log, say x, from the generator g and g^x . The most effective attack on the Discrete Logarithm Problem is the Index Calculus Method. In the present study the performance of Random method, which is one of the primitive method of Index Calculus Method is investigated. A parameter, which is influencing the running time of this method is identified and the performance is improved through the same parameter. Also, a partial linear sieve method, which is derived from the well known linear sieve and Pollard Rho method is introduced and analyzed. The partial linear sieve and Random methods are compared based on their running time. It is observed that a range parameter is influencing the running time of the partial linear sieve method, which leads to outperform the partial linear sieve method than the Random method. This range parameter is introduced in the Random method, due to which the probability of numbers getting smoothening is improved. It is shown that the performance of Random method is enhanced by more than 50% for problems of size ≈ 20 digits.

Keywords and phrases:

• Discrete logarithm problem
• index calculus method
• random method