Anlysis of the Lenstra Elliptic Curves Factorization Method

Author Name(s): *Albert I. Galiev, Shamil T. Ishmukhametov, Ramilya G. Rubtsova
Author Email: *crowbar_al@mail.ru

Abstract

The problem of factoring a composite natural number into the product of prime factors is a hard computational problem. This problem lies in the base of the well-known open-key RSA cyphering algorithm. In the paper we investigate Lenstra’s Elliptic Curves Factoring Algorithm, which is the third (after the Number Field Sieve and the Quadratic Sieve) by speed algorithm in the world classification of factoring algorithms. Moreover, the speed of this algorithm depends mostly on the size of the minor factor, so it can be applied to very large record numbers. Original Lenstra’s algorithm of 1987 year consisted of one stage while later it was shown that in many cases it is more effectively to use the two-stage version.But when we are able to use multi-processors systems, we can arrange parallel computations which use different versions of the basic algorithm and are more effective. In the paper, we consider several improvements tothe LenstraBasic Algorithm and compare them by speed. In particular, we study the special Montgomery presentation of elliptic curves and show that they give a considerable acceleration of the factoring procedure. We measure the speed of four realizations of Lenstra’s algorithm to choose the best one.

Introduction

Elliptic curves have become very popular in number theory and algebraic geometry in connection with their applications to cryptography. Such applications became possible after independent publications by Neil Koblits[1] and Victor Miller [2]in 1985.These works made the beginning of a series of studies on the use of elliptical curves in cryptography

A detailed exposition of the theory of elliptic curves and their applications in cryptography can be found in the article [3] and the monograph [4]. The monograph [5] describes cryptographic protocols using elliptic curves. The reason why elliptic curves have received interest from cryptographers is that the problem of discrete logarithm on elliptic curves considered over finite fields (that is, computing the multiple x for two given points of the curve  ), is much more difficult to solve from the computational viewpoint than the analogous problem for the factorization of integers or the calculation of the discrete logarithm in finite fields. This led to the fact that with less computational costs and greater cryptographic stability, it was possible to accomplish the tasks of encryption and constructing digital signatures, using elliptic curves.

Hendrik Lenstra in his article of 1987 [6] gave a description of a new subexponential algorithm of factorization, which was included in the three fastest algorithms of factorization. The advantage of this algorithm is also that its computational complexity depends only on the size of the minimum divisor, and not on the size of the factorized number. T.Ishmukhametovin the monograph [7] gives a detailed description of the main algorithms of factorization, known to date. This article considers four modifications of the Lenstra algorithm: the classical algorithm in affine coordinates, proposed by Lenstra and consisting of one stage, the algorithm with two stages, the algorithm in projective coordinates, and the Montgomery method. The study of this article continues the study of the article [8].

Conclusion

Summarizing, it is possible to estimate the speed of operation of the four algorithms having been considered. The undisputed leader is the Montgomery method, which among all the studies considered in this article was the fastest and most optimal one. The use of projective coordinates instead of affine coordinates also gives a significant speed increase due to reduction in the number of operations for computing the inverse elements.Comparison between algorithms with one stage and two ones gives preference to the second algorithm, however, this gain could be much larger if the initial boundary could be chosen efficiently. Inefficient choose of can be reduced by using parallelization of the algorithm into several threads. Another reserve for accelerating the algorithm is the possibility of usingthecurves of Edwards [12] to further reduce modular operations.

References

  1. Koblitz N.,Introduction to elliptic curves and modular forms, Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1984.
  2. Miller V.,Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO 85, Springer Lecture Notes in Computer Science vol. 218, 1985, p. 418-425
  3. Koblitz, Menezes A., Vanstone S. The State Of Elliptic Curve Cryptography/ Kluwer Academic Publishers, Boston, 2000, p. 104-105
  4. Washington L. Elliptic Curves Number Theory and Cryptography/ Washington. – Series Discrete Mathematics and Its Applications, Chapman &Hall/ CRC, second ed. (2008).
  5. Blake I.F., Seroussi G., Smart N.P. Advances in Elliptic Curve Cryptography // Cambridge Univ.Press, London Mathematical Society Lecture Note Series. 317 (2005)
  6. Lenstra H.W. Factoring integers with elliptic curves/W.Lenstra.–Ann.Math. v.126 (1987), p. 649–674
  7. Ishmukhametov S.Т. TheMethods of Factorization of Natural Numbers /Т.Ishmukhametov. – Kazan, 2011, p. 89
  8. Ismail Amer, ShamilT.Ishmukhametov, Ramilya G. Rubtsova. Lenstra Factorization Method Convergence Investigation on Elliptic Curves//Research Journal of Applied Sciences 10 (8), 358-364, 2015
  9. Crandall R. and Pomerance C. The Prime Numbers: A Computational Perspective (Springer–Verlag, Berlin, New York, 2005), 2-nd ed.
  10. Brent R.P. Some integer factorization algorithms using elliptic curves/R.P. Brent.– Austral.Comput.Sci.Comm, 1986, v. 8, p. 149–163
  11. Brent R.P., Crandall R.E., Dilcher K., Van Halewyn C. Three New Factors Of Fermat Numbers / Mathematics Of Computation Volume 69, Number 231, 2000, Pages 1297–1304
  12. Edwards H.M. A normal form for elliptic curves./ H.M. Edwards.–Bull. Amer. Math. Soc. 44 (2007), p. 393-422

 

1,385 total views, no views today

Download PDF File

About the author: admin