ISSN:
1573-7586
Keywords:
elliptic curve
;
discrete logarithm
;
Xedni calculus
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The xedni calculus attack on the elliptic curve discrete logarithm problem (ECDLP) involves lifting points from the finite field $${\mathbb{F}}_p$$ to the rational numbers $${\mathbb{Q}}$$ and then constructing an elliptic curve over $${\mathbb{Q}}$$ that passes through them. If the lifted points are linearly dependent, then the ECDLP is solved. Our purpose is to analyze the practicality of this algorithm. We find that asymptotically the algorithm is virtually certain to fail, because of an absolute bound on the size of the coefficients of a relation satisfied by the lifted points. Moreover, even for smaller values of p experiments show that the odds against finding a suitable lifting are prohibitively high.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008312401197
