Computational studies on discrete logarithm problem

Abstract

The broad objective of the present work is computational analysis on the mathematically hard Discrete Logarithm Problem(DLP). The DLP forms the basis for several popular public key cryptosystems. For a given prime number p, a generator g and#8712; Zand#8727;p and an element y and#8712; Zand#8727;p , the problem of finding an x (0 and#8804; x and#8804; p and#8722; 2) such that gx and#8801; y mod p is known as the DLP. The DLP is also defined over other groups. There are several methods to solve the DLP and the Index Calculus Method (ICM) is currently the best general-purpose algorithm. A more specific objective of the thesis is the investigation of the ICM. The ICM has two stages: a pre-computation stage where logarithms of the elements of a subset of the group, known as a factor base, are computed, and a solution stage where the desired logarithm is computed with the help of pre-computed logarithms of the factor base. The pre-computation stage itself has two steps. The first is generating the necessary linear system of equations and the second is solving the linear system. Linear sieve is a popular method for ICM and is used for efficiently generating the equations relating the logarithms of the elements in the factor base. However, the method generates a large system that is normally reduced (by using structured Gaussian elimination or other techniques) to yield a faster solution. There are several computational parameters such as the factor base and its size and the sieve length to be used in linear sieve that have been shown in literature to have an impact on the overall performance of the ICM. The first major contribution is the development of a new technique by combining the size of the factor base and the sieve length to achieve a performance improvement of 30% and more for the pre-computation step on problem sizes of over 120 bits. Another contribution is the extension of the concept of smooth numbers over factor bases and finite fields. This new concept is used for improving the solutions for certain instances of the DLP previously assumed to be hard..