Show simple item record

dc.contributor.advisorVeni Madhavan, C E
dc.contributor.authorVivek, Srinivas V
dc.date.accessioned2013-05-21T07:29:04Z
dc.date.accessioned2018-07-31T04:38:21Z
dc.date.available2013-05-21T07:29:04Z
dc.date.available2018-07-31T04:38:21Z
dc.date.issued2013-05-21
dc.date.submitted2010-08
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/1996
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/2584/G24423-Abs.pdfen_US
dc.description.abstractThere 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 109en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG24423en_US
dc.subjectComputational Mathematicsen_US
dc.subjectComputational Number Theoryen_US
dc.subjectNumber Theoryen_US
dc.subjectCubic Sieve Congruence (CSC)en_US
dc.subjectDiscrete Logarithm Problem (DLP)en_US
dc.subjectCryptanalysisen_US
dc.subjectDiophantine Equationen_US
dc.subjectContinued Fractionen_US
dc.subjectFractional Part Inequalityen_US
dc.subjectFractional Part Sequencesen_US
dc.subject.classificationComputer Scienceen_US
dc.titleOn A Cubic Sieve Congruence Related To The Discrete Logarithm Problemen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record