Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/4252
Title: Computational studies on discrete logarithm problem
Researcher: Padmavathy, S
Guide(s): Chakravarthy, Bhagvati
Keywords: Index Calculus Method
Public key cryptography
Linear sieve method
Upload Date: 16-Aug-2012
University: University of Hyderabad
Completed Date: 2009
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..
Pagination: 163p.
URI: http://hdl.handle.net/10603/4252
Appears in Departments:Department of Computer & Information Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File84.61 kBAdobe PDFView/Open
02_certificate.pdf29.44 kBAdobe PDFView/Open
03_declaration.pdf29.09 kBAdobe PDFView/Open
04_acknowledgements.pdf29.97 kBAdobe PDFView/Open
05_contents.pdf95.63 kBAdobe PDFView/Open
06_list of figures.pdf45.69 kBAdobe PDFView/Open
07_list of tables.pdf48.06 kBAdobe PDFView/Open
08_abstract.pdf82.7 kBAdobe PDFView/Open
09_chapter 1.pdf199.92 kBAdobe PDFView/Open
10_chapter 2.pdf473.68 kBAdobe PDFView/Open
11_chapter 3.pdf359.3 kBAdobe PDFView/Open
12_chapter 4.pdf438.74 kBAdobe PDFView/Open
13_chapter 5.pdf407.11 kBAdobe PDFView/Open
14_chapter 6.pdf460.85 kBAdobe PDFView/Open
15_chapter 7.pdf142.9 kBAdobe PDFView/Open
16_chapter 8.pdf75.44 kBAdobe PDFView/Open
17_bibliography.pdf166.5 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.