Improved random method using smooth numbers over Zp*

International Journal of Applied Mathematics and Computation

Rajasekaran Padmavathy²  Chakravarthy Bhagvati¹ 

[1] Department of Computer and Information SciencesUniversity of Hyderabad, Hyderabad, INDIA$$;Department of Computer Science and EngineeringNational Insitute of Technology, Warangal, INDIA$$

关键词: Cryptanalysis;    Discrete Logarithm Problem;    Index Calculus Method;    Random method;    Smooth numbers over $Z_p^{*}$.;   

DOI  :  10.0000/ijamc.2010.2.3.78

来源: PSIT Kanpur

【 摘 要 】

The Index Calculus Method(ICM) is the most effective attack on the mathematical hard problem, namely Discrete Logarithm Problem (DLP). The ICM has two steps: A pre-computation step and an individual logarithm computation step. In the pre-computation step, the logarithms of elements of a subset of a group known as factor base is computed and in the individual logarithm step, the DLP is computed with the help of pre computed logarithms of factor base. The pre-computation of ICM is based on the probability of field elements getting smoothening i.e., the factors of field elements are less than a prescribed bound. In the present work the ICM is improved  through the property of smoothness concept over the the prime field $Z_p^{*}$ for certain instances of primes. This new smoothness concept is introduced and found to exhibit different characteristics on some types of primes. The property based on the characteristics of smooth numbers over $Z_p^{*}$ allows to map the field elements from one subset to another. Based on this concept an improved ICM by increasing the probability of numbers getting smoothening is devised. The efficiency of the improved ICM is analyzed experimentally. Through the experimental results it is observed that the performance of ICM is enhanced by $approx 50\%$.

【 授权许可】

Unknown