# American Institute of Mathematical Sciences

August  2017, 11(3): 453-469. doi: 10.3934/amc.2017038

## Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm

 1 Mathematics Department, University of Auckland, New Zealand 2 College of Information Engineering, Shenzhen University, Shenzhen 518060, China 3 School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China

* Corresponding author

Received  June 2015 Revised  February 2016 Published  August 2017

Fund Project: This work was supported by the National Natural Science Foundation of China (No. 61672550,61402293).

The negation map can be used to speed up the computation of elliptic curve discrete logarithms using either the baby-step giant-step algorithm (BSGS) or Pollard rho. Montgomery's simultaneous modular inversion can also be used to speed up Pollard rho when running many walks in parallel. We generalize these ideas and exploit the fact that for any two elliptic curve points X and Y, we can efficiently get X-Y when we compute X+Y. We apply these ideas to speed up the baby-step giant-step algorithm. Compared to the previous methods, the new methods can achieve a significant speedup for computing elliptic curve discrete logarithms in small groups or small intervals.

Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange's "grumpy giants and a baby" algorithm, and also to consider this algorithm in the case of groups with efficient inversion.

Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho. Furthermore, for the discrete logarithm problem in an interval, the interleaved BSGS algorithm is considerably faster than the Pollard kangaroo or Gaudry-Schost methods.

Citation: Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038
##### References:

show all references

##### References:
Graph of $c(t) t^2$ for $t \in [0,1]$ obtained by simulations for the three values $M = \sqrt{N/2}, M = \sqrt{N}$ and $M = \tfrac{1}{2}\sqrt{N}$. The multiple lines denote the results for different experiments coming from different choices of $N$
Graph of $c(t) t^2$ for $t \in [0,1]$ obtained by simulations, for grumpy giants method using $x$-coordinates, with $M = \sqrt{N/2}$ and $M = \sqrt{N}$
Size of set $\mathcal{L}_L$ written as $c(t) L^2$ where $t = L/\sqrt{N}$.
 $t$ 0 0.12 0.24 0.37 0.49 0.61 0.73 0.85 0.97 $c(t)$ 3 3 3 2.99 2.79 2.3 1.77 1.35 1.06
 $t$ 0 0.12 0.24 0.37 0.49 0.61 0.73 0.85 0.97 $c(t)$ 3 3 3 2.99 2.79 2.3 1.77 1.35 1.06
Results of experiments with the grumpy-giants algorithm without negation
 Bits #Elliptic Curves #DLPs per Curve average value for c standard deviation 28 100 10000 1.2579 0.0083 29 100 10000 1.2533 0.0064 30 100 10000 1.2484 0.0062 31 100 10000 1.2517 0.0067 32 100 10000 1.2736 0.0054
 Bits #Elliptic Curves #DLPs per Curve average value for c standard deviation 28 100 10000 1.2579 0.0083 29 100 10000 1.2533 0.0064 30 100 10000 1.2484 0.0062 31 100 10000 1.2517 0.0067 32 100 10000 1.2736 0.0054
The table lists constants $c$ such that the named algorithm requires $(c + o(1)) \sqrt{N}$ group operations for large enough groups of size $N$. The first block lists algorithms for general groups, and all these results are known (see Section 2). The values for the grumpy-giant algorithm (marked by an asterisk) are conjectural and the values for the rho and Gaudry-Schost algorithm are heuristic. The second block lists algorithms for groups having an efficiently computable inversion (see Section 3). Some of these results are new (the first one appears as an exercise in the first author's textbook). The third block lists algorithms that exploit efficient inversion as well as our main observation, and these results are all new (see Section 5)
 Algorithm Average-case Worst-case Textbook BSGS [19] $1.5$ $2.0$ Textbook BSGS optimised for average-case [18] $1.414$ $2.121$ Pollard interleaving BSGS [17] $1.333$ $2.0$ Grumpy giants [2] $1.25^*$ $\le 3$ Pollard rho using distinguished points [20] $1.253$ $\infty$ Gaudry-Schost [7] $1.661$ $\infty$ BSGS with negation $1.0$ $1.5$ Pollard interleaving BSGS with negation $0.943$ $1.414$ Grumpy giants with negation $0.9^*$ $\le 2.7$ Pollard rho using negation [3,21] $0.886(1 + o(1))$ $\infty$ Gaudry-Schost using negation [8] $1.36$ $\infty$ Interleaved BSGS with block computation $0.38$ $0.57$ Grumpy giants with block computation $0.36^*$ $\le 1.08$ Pollard rho with Montgomery trick $0.47$ $\infty$ Gaudry-Schost with Montgomery trick $0.72$ $\infty$
 Algorithm Average-case Worst-case Textbook BSGS [19] $1.5$ $2.0$ Textbook BSGS optimised for average-case [18] $1.414$ $2.121$ Pollard interleaving BSGS [17] $1.333$ $2.0$ Grumpy giants [2] $1.25^*$ $\le 3$ Pollard rho using distinguished points [20] $1.253$ $\infty$ Gaudry-Schost [7] $1.661$ $\infty$ BSGS with negation $1.0$ $1.5$ Pollard interleaving BSGS with negation $0.943$ $1.414$ Grumpy giants with negation $0.9^*$ $\le 2.7$ Pollard rho using negation [3,21] $0.886(1 + o(1))$ $\infty$ Gaudry-Schost using negation [8] $1.36$ $\infty$ Interleaved BSGS with block computation $0.38$ $0.57$ Grumpy giants with block computation $0.36^*$ $\le 1.08$ Pollard rho with Montgomery trick $0.47$ $\infty$ Gaudry-Schost with Montgomery trick $0.72$ $\infty$
Size of set $\mathcal{L}_L$ written as $c(t) L^2$ where $t = L/\sqrt{N}$
 $t$ 0 0.15 0.3 0.46 0.61 0.76 0.91 $c(t)$ 6 5.76 5.47 4.1 2.56 1.72 1.2
 $t$ 0 0.15 0.3 0.46 0.61 0.76 0.91 $c(t)$ 6 5.76 5.47 4.1 2.56 1.72 1.2
Results of experiments with the grumpy-giants algorithm exploiting efficient inversion
 Bits #Elliptic Curves #DLPs per Curve average value for c standard deviation 28 100 10000 0.8926 0.0077 29 100 10000 0.9053 0.0061 30 100 10000 0.8961 0.0073 31 100 10000 0.9048 0.0068 32 100 10000 0.9207 0.0065
 Bits #Elliptic Curves #DLPs per Curve average value for c standard deviation 28 100 10000 0.8926 0.0077 29 100 10000 0.9053 0.0061 30 100 10000 0.8961 0.0073 31 100 10000 0.9048 0.0068 32 100 10000 0.9207 0.0065
Results of experiments with the 4-giants algorithm without negation
 Bits #Elliptic Curves #DLPs per Curve average value for $c$ 28 100 10000 1.2867 29 100 10000 1.3002 30 100 10000 1.2926 31 100 10000 1.2944 32 100 10000 1.3150
 Bits #Elliptic Curves #DLPs per Curve average value for $c$ 28 100 10000 1.2867 29 100 10000 1.3002 30 100 10000 1.2926 31 100 10000 1.2944 32 100 10000 1.3150
 [1] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [2] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [3] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [4] Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339 [5] João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138 [6] Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319 [7] Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375 [8] Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166 [9] Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269 [10] Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 [11] Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436 [12] Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318 [13] Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340 [14] Yongxiu Shi, Haitao Wan. Refined asymptotic behavior and uniqueness of large solutions to a quasilinear elliptic equation in a borderline case. Electronic Research Archive, , () : -. doi: 10.3934/era.2020119 [15] Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469

2019 Impact Factor: 0.734