Record Details

On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem
 
Creator Vivek, Srinivas V
 
Subject Computational Mathematics
Computational Number Theory
Number Theory
Cubic Sieve Congruence (CSC)
Discrete Logarithm Problem (DLP)
Cryptanalysis
Diophantine Equation
Continued Fraction
Fractional Part Inequality
Fractional Part Sequences
Computer Science
 
Description There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy

x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα ,

where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC.
This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109
 
Contributor Veni Madhavan, C E
 
Date 2013-05-21T07:29:04Z
2013-05-21T07:29:04Z
2013-05-21
2010-08
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/1996
http://etd.ncsi.iisc.ernet.in/abstracts/2584/G24423-Abs.pdf
 
Language en_US
 
Relation G24423