Paper Info
Title
Time-Memory Trade-offs for Index Calculus in Genus 3.
Abstract
In this paper, we present a variant of Diem's p (O) over tilde (q) index calculus algorithm to attack the discrete logarithm problem (DLP) in Jacobians of genus 3 non-hyperelliptic curves over a finite field F-q. We implement this new variant in C++ and study the complexity in both theory and practice, making the logarithmic factors and constants hidden in the p (O) over tilde -notation precise. Our variant improves the computational complexity at the cost of a moderate increase in memory consumption, but we also improve the computational complexity even when we limit the memory usage to that of Diem's original algorithm. Finally, we examine how parallelization can help to reduce both the memory cost per computer and the running time for our algorithms.
Year
DOI
Venue
2015
10.1515/jmc-2014-0033
JOURNAL OF MATHEMATICAL CRYPTOLOGY
Keywords
DocType
Volume
Discrete logarithm problem,index calculus,double large prime,higher genus,genus 3,non-hyperelliptic curve,quartic curve,plane curve,time-memory trade-off
Journal
9
Issue
ISSN
Citations 
2
1862-2976
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Kim Laine1939.83
Kristin Lauter2188398.23