Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Solving ECDLP over F p with Pre-computation via Representation Technique

Abstract : We present a new algorithm solving the elliptic curve discrete logarithm problem (ECDLP) with pre-computation. Our method is based on recent work from Delaplace and May (NuTMiC 2019) which aims to solve ECDLP over some quadratic field F p 2 using the so-called representation technique. We first revisit Delaplace and May's algorithm and show that with better routines, it runs in time p, improving on the p 1.314 time complexity given by the authors. Then, we show that this method can be converted to a p 4/5-algorithm, assuming that we have performed a p 6/5-pre-computation step in advance. Finally, we extend our method to other fields F p , where ≥ 2 is a constant, leading to a p 2 /(2 +1)-algorithm, after a p (+1)/(2 +1)-pre-computation step. Although our method does not improve on previous ECDLP with pre-computation algorithm (namely the one from Bernstein and Lange), we think it offers an elegant alternative, which can hopefully lead to further improvements, the idea of using the representation technique for ECDLP being very new.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-02427655
Contributor : Claire Delaplace <>
Submitted on : Friday, January 3, 2020 - 7:03:30 PM
Last modification on : Thursday, January 7, 2021 - 4:34:49 PM
Long-term archiving on: : Monday, April 6, 2020 - 4:54:30 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02427655, version 1

Citation

Claire Delaplace, Pierre-Alain Fouque, Paul Kirchner, Alexander May. Solving ECDLP over F p with Pre-computation via Representation Technique. 2020. ⟨hal-02427655⟩

Share

Metrics

Record views

128

Files downloads

487