Article (Scientific journals)
Cubic Sieve Congruence of the Discrete Logarithm Problem, and fractional part sequences
Venkatesh, Srinivas Vivek; C. E. Veni Madhavan
2014In Journal of Symbolic Computation, 64, p. 22-34
Peer Reviewed verified by ORBi
 

Files


Full Text
csc_fps_jsc-final.pdf
Author postprint (482.17 kB)
Download

The final publication is available at http://www.sciencedirect.com/science/article/pii/S0747717113001703.


All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Computational number theory; Cryptanalysis; Diophantine equation; Discrete Logarithm Problem; Fractional part sequence
Abstract :
[en] The Cubic Sieve Method for solving the Discrete Logarithm Problem in prime fields requires a nontrivial solution to the Cubic Sieve Congruence (CSC) $ x^3 \equiv y^2 z (mod p) $, where 'p' is a given prime number. A nontrivial solution must also satisfy $ x^3 \neq y^2 z $ and $ 1 <= x,y,z < p^a $, where 'a' is a given real number such that $ 1/3 < a <= 1/2 $. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC. CSC can be parametrized as $ x \equiv v^2 z (mod p) $ and $ y \equiv v^3 z (mod p) $. In this paper, we give a deterministic polynomial-time ($ O(ln^3 p) $ bit-operations) algorithm to determine, for a given 'v', a nontrivial solution to CSC, if one exists. Previously it took $ õ(p^a) $ time in the worst case to determine this. We relate the CSC problem to the gap problem of fractional part sequences, where we need to determine the non-negative integers 'N' satisfying the fractional part inequality $ {\theta N} < \phi $ ($ \theta $ and $ \phi $ are given real numbers). The correspondence between the CSC problem and the gap problem is that determining the parameter 'z' in the former problem corresponds to determining 'N' in the latter problem. We also show in the $ a = 1/2 $ case of CSC that for a certain class of primes the CSC problem can be solved deterministically in $ õ(p^{1/3}) $ time compared to the previous best of $ õ(p^{1/2}) $. It is empirically observed that about one out of three primes is covered by the above class.
Disciplines :
Computer science
Author, co-author :
Venkatesh, Srinivas Vivek ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
C. E. Veni Madhavan;  Indian Institute of Science, Bangalore, India > Department of Computer Science and Automation
External co-authors :
yes
Language :
English
Title :
Cubic Sieve Congruence of the Discrete Logarithm Problem, and fractional part sequences
Publication date :
2014
Journal title :
Journal of Symbolic Computation
ISSN :
1095-855X
Publisher :
Academic Press
Volume :
64
Pages :
22-34
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBilu :
since 31 August 2015

Statistics


Number of views
96 (2 by Unilu)
Number of downloads
134 (1 by Unilu)

Scopus citations®
 
0
Scopus citations®
without self-citations
0
OpenCitations
 
0
WoS citations
 
0

Bibliography


Similar publications



Contact ORBilu