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