I. INTRODUCTION

The factorization of a natural number or its decomposition into simple multipliers belongs to the main problems of the modern theory of numbers [1][2][3], various forms of the system of residual classes [4,5] and plays an important role in cryptographic information security systems [6][7][8]. As a rule, large-scale computing and time resources are required for the expansion of the multiplicity of the number obtained as a result of the product of two large prime numbers [9].

This circumstance is used in cryptographic algorithms as protection against potential hacking attempts: for the creation and multiplication of two prime numbers of large bits, it does not require significant costs [10], and their factorization is a long and laborious process. Despite the considerable efforts of scientists in this direction, to date, there are no quantum algorithms for factorizing multi-digit numbers, which allow executing the timetable for the multipliers at a practical time. But the proof that there is no solution to this problem in polynomial time is also absent [11].

Particular interest to the factorization problem was the emergence of cryptographic algorithm encryption RSA, which uses its computational complexity [12].

The decomposition of numbers containing in a binary record up to 768 bits inclusive was obtained for polynomial time by the modern methods (in particular, the general method of the numerical field sieve) [13]. However, further increase in the dimension significantly increases the complexity of the scheduling operation of a composite number. In connection with this, it is necessary to develop other approaches to solving the problem of factorization of integers.

II. FERMAT'S FACTORIZATION METHOD

Fermat's method is the most widely used method [11], which is based on the search for pairs of natural numbers А and В, for which equality n=A 2 -B 2 is performed, where n=p⋅q is known integer, which is the product of two unknown primes p and q, which should be found.

For this purpose [ ]

n m =

is searched and then the parameter f(x)=(m+x) 2 -n is calculated, where x=1, 2, 3, … , as long as some value f(x) will not be equal to the full square of a number, for example В 2 .

Then, respectively, А 2 =(m+x) 2 and the desired decomposition will be n=p⋅q= А 2 -В 2 =(А-В)(А+В).

The most computable complex operations in this case are elevation to a square and the search for a square root. In [14], an improved Fermat's factorization method is proposed, where the condition is used that squares of integers can be represented as a sum of odd numbers, the number of which is equal to this number:

( ) ∑ = − = s i i s 1 2 1 2

.

(1) Therefore, having found m та f1(x)=f(x) when х=1, the following steps occur according to the expression fi=fi-1+2(m+i)-1, where і=2, 3, 4, … as long as fi will not be a full square of a certain number.

The decomposition for multipliers will be determined by this expression: n=(m+i-fi)( m+i+fi). Table 1 provides an example of factorization using the classical and improved Fermat's method for n=4717

( [ ]684717 1 = = m

). Thus the decomposition of the number 4717 on simple multipliers is obtained: 4717=71 2 -18 2 =(71+18)(71-18)=89⋅53. It should be noted that the number of iterations in both methods is the same. However, in the improved Fermat's method, the operation of elevating to a square of large numbers is excluded. In addition, arithmetic operations are performed over numbers of a much smaller digit than the classical ones. But the most computationally labor-intensive operation is the extraction of a square root.

Therefore, the purpose of our work is to develop a factorization algorithm based on the Fermat's method, in which there will be no square root search operation, which is especially important for work with numbers of large bit rate for the experimental study, as well as an experimental study of the time characteristics of the software implementation of the Fermat's method, its modification and the proposed algorithm.

III. DESCRIPTION OF THE PROPOSED FACTORIZATION ALGORITHM

The property ( 1) is also used in the proposed algorithm, the parameters m1=m and f11=f1 are calculated similarly to the previous case. Then the sequence of operations f1і=f1 і-1-r1 і-1, r11=1, r1 і-1=2i-3=r1 і-2+2, i=2, 3, … are performed until the condition for some і is not fulfilled: f1і-r1і≤0.

(2) Further calculations occur in such a way when performing a strict inequality (2): m2=m1+1; f21=f1і+2 m2+1-r1і, r21=r1і+2. Searching for the following values f2і, r2і is carried out in the same way as the previous case. In the general case, these calculations can be described by the following expressions: fj і+1= fjі-rjі≤0, rj i+1=rjі+2, if fjі-rjі>0;

(3) are determined which will be a positive integer, the desired quantity, which will be a natural number.

fj+1 1= fjі+2mj+1-rjі≤0, rj i+1=rjі+2, if fjі-rjі<0. (4

It should be noted that in this case the value of the parameter j corresponds to the number of steps in the classical and improved Fermat's method.

  n n q − = 2 r1=1   1 2 2 + ⋅ = n r q= q+r2 r1= r1+2 q = q -r1 q-r1> r1+2 r2= r2+2 q=0 (r2-1)/2-(r1-1)/2 end

Consequently, the decomposition of the number 4717 into simple multipliers are carried out in this way:

( )

18 4717 3 68 2 = − + = B , 4717=71 2 -18 2 =(71+18)⋅ ⋅(71- 18)=89⋅53

. This procedure is performed without the use of a computationally cumbersome operation extracting the square root. Additionally, addition and subtraction are performed over smaller numbers than in the two previous methods, although the number of these operations is greater.

IV. EXPERIMENTAL STUDY OF TIME CHARACTERISTICS OF FACTORIZATION METHODS

The multiplier р was chosen to be fixed and equal to the largest prime number of a certain bit rate for the experimental study of the factorization of the number n=p⋅q.

Then, a number of prime numbers of the same digit are determined that of p, of which 1000 values for the number q were selected uniformly in the order of growth.

After multiplying p by q, the timer fixed the factorization time for each of the 1000 received products. The time characteristics of the software implementation of the classical (curve 1) and improved (curve 2) Fermat's methods, as well as the proposed algorithm (curve 3) are presented in Figures 2 and 3 for the bit rates 30 (р=1073741789) and 32 (р=4294967291) bits respectively. All calculations were carried out on a portable computer Lenovo B50-70 with processor Intel Pentium 3558U (1.7 GHz). The amount of RAM in the device was 4 GB. When designing the computing software, a high level programming language C ++ was selected, which allows you to transform the codes into different architectures and operating systems.

All graphics are descending character, indicating a decrease in the factorization time with a decrease in the difference between the multipliers, whose product is factorized. The proposed algorithm, whose time reduction is linear, has an advantage over the other two at small values of q. With increasing q the least time is characterized by an improved Fermat's algorithm.

Further growth of q leads to the fact that the proposed algorithm uses the most time compared to the other two. It should be noted that with increasing the bit rate number of the point of intersection of the straight line with the curves obtained by using the Fermat's method, are shifted to the left on the graphs.

Figure 4 depicts the graphs of the dependence of the average factorization time of three methods on the bit rate number for 1000 values selected by the above-described method. It can be seen that all graphs grow in parabolic law with increasing bit rate. The least average factorization time is characterized by an improved Fermat's algorithm, and the largest one is classical. Fig. 4. Graphs of the dependence of the average factorization time on the number of digits: 1 -the classical Fermat's method; 2 -an improved Fermat's method; 3 -the proposed algorithm Consequently, it is advisable to apply the proposed method when there is a big difference between the numbers whose product is to be factorized.

The Table 3 shows the results of the factorization of the product of two prime numbers for a fixed р=3571 and a variable q (t1 -the classical Fermat's method, t2 -the improved Fermat's method, t3 -the proposed algorithm).

It can be seen from the Table 3 that the improved Fermat's method increases the speed factorization approximately into 1.1-1.2 times, and the proposed method -into 5-11 times compared with the classical Fermat's method.