dc.contributor.advisor Veni Madhavan, C E dc.contributor.author Vivek, Srinivas V dc.date.accessioned 2013-05-21T07:29:04Z dc.date.accessioned 2018-07-31T04:38:21Z dc.date.available 2013-05-21T07:29:04Z dc.date.available 2018-07-31T04:38:21Z dc.date.issued 2013-05-21 dc.date.submitted 2010-08 dc.identifier.uri http://etd.iisc.ac.in/handle/2005/1996 dc.identifier.abstract http://etd.iisc.ac.in/static/etd/abstracts/2584/G24423-Abs.pdf en_US dc.description.abstract 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 en_US dc.language.iso en_US en_US dc.relation.ispartofseries G24423 en_US dc.subject Computational Mathematics en_US dc.subject Computational Number Theory en_US dc.subject Number Theory en_US dc.subject Cubic Sieve Congruence (CSC) en_US dc.subject Discrete Logarithm Problem (DLP) en_US dc.subject Cryptanalysis en_US dc.subject Diophantine Equation en_US dc.subject Continued Fraction en_US dc.subject Fractional Part Inequality en_US dc.subject Fractional Part Sequences en_US dc.subject.classification Computer Science en_US dc.title On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.discipline Faculty of Engineering en_US
﻿