Research Journal of Applied Sciences

Year: 2015
Volume: 10
Issue: 8
Page No. 365 - 370

Lenstra Factorization Method Convergence Investigation on Elliptic Curves

Authors : Ismail Amer, Shamil T. Ishmukhametov and Ramilya G. Rubtsova

Abstract: It is well known that the process of natural numbers decomposition in a product of primefactors (factorization) is a time-consuming computational procedure. This property is widely used in cryptography. In particular, the known RSA encryption method uses a composite number n of 1024 bits or more which is the product of two prime numbers as the secret key. One of the most effective methods of integer factorization is H. Lenstry Method based on the arithmetic of elliptic curves. This method has the following feature: its capacity does not depend on the size of the original number n but on the size of the smallest divisor n. Therefore, the Lenstra allows to factoring the numbers that are inaccessible for other methods. The peculiarity of Lenstra Method is its heavy dependence on the choice of an elliptic curve. More precisely, the algorithm selects an arbitrary curve over a prime field of the characteristic p where p is the unknown divisor n. Let t is the number of points on a selected curve. The rate of algorithm convergence depends on the greatest prime number dividing the number t. For example if , the decomposition of t in the product of prime factors, then the method complexity depends on B = maxi . Due to the fact that the method success depends heavily on t value and its factors which which is the subject of luck. The worst case occurs if t is a prime number. To eliminate obviously bad cases, you must start the factorization procedure simultaneously on several different curves. Such parallelism allows you to find the curve on which the process will converge faster than the others. The problem is that the selection of too many curves will affect the overall performance of the method and an insufficient number of curves does not guarantee a result. In this study, we investigate the convergence of Lenstra factorization method, depending on the choice of an elliptic curve on which the factorization procedure is performed more effectively. We study the statistical distribution of “good” curves on which the factorization procedure is performed more efficiently.

How to cite this article:

Ismail Amer, Shamil T. Ishmukhametov and Ramilya G. Rubtsova, 2015. Lenstra Factorization Method Convergence Investigation on Elliptic Curves. Research Journal of Applied Sciences, 10: 365-370.

Design and power by Medwell Web Development Team. © Medwell Publishing 2022 All Rights Reserved