Formation of non-uniformity increment for the basic module base in the problem of Fermat’s factorization method

Abstract

One way to ensure the specified level of information security is the use of asymmetric encryption algorithms. The cryptographic durability of such algorithms is based on the difficulty of execution the factorization problem. Modern methods of decomposition of multiple-bit sequences at factors are based on the fundamental concepts of classical Fermat's factoring algorithm. Some of the possible directions of the acceleration Fermat’s method include reducing the number of arithmetically complex operations extracting the square root. The modular division procedure using several module bases (the sieve method) allows you to exclude from consideration the options of acceptable values of X, which do not satisfy the condition Х²=N+Y. In the process of research the modification Fermat's factorization method it has been determined that it is possible to use not the pre-sieved high values of X during the search for a solution of equation Y²= X²-N, but increments to them that are the small numbers. A method of forming a non-uniform incremental data for the valid values of X relation to the basic module base during the factorization of numbers with Fermat's method is offered. It can significantly reduce the number of scanned values. Furthermore, the use of this algorithm provide not more than one addition operation of multi-bit numbers. All other operations are carried out with small numbers usually not exceeding 2¹⁵.