The Method of Factorizing Multi-Digit Numbers Based on the Operation of Adding Odd Numbers

Abstract

The method for factorizing multi-digit numbers based on the addition of odd numbers is developed in this article. The temporal characteristics of software implementations of the proposed method, the classical Fermat method and its improvement are experimentally investigated. It is revealed that the proposed algorithm, whose time reduction is linear, has an advantage over the other two with a large difference between the multipliers that are factorized. Other dependencies are declining parabolic.

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-3 ], various forms of the system of residual classes [ 4, 5 ] and plays an important role in cryptographic information security systems [ 6-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=A2-B2 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 m = [ n ] 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 s2 = ∑ (2i − 1)

i=1 . (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 ( m1 = [ 4717 ]= 68 ). Thus the decomposition of the number 4717 on simple multipliers is obtained:

4717=712-182=(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.

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.

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; fj+1 1= fjі+2mj+1-rjі≤0, rj i+1=rjі+2, if fjі-rjі<0.

Under the condition fjі-rjі=0, the desired quantities А=(m+j) and B = (m + j)2 − n are determined which will be a positive integer, the desired quantity, which will be a natural number.

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.

Fig. 1 shows a block diagram of the developed algorithm, and in the Table 2, the corresponding example is presented (2) (3) (4) for n=53⋅89=4717 ( m1 = [ 4717 ]= 68).

begin n

2 q =  n  − n

r1=1 r2 =  n ⋅ 2 + 1 q= q+r2

Consequently, the decomposition of the number 4717 into simple multipliers are carried out in this way: 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. 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. 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571 3571

V. CONCLUSIONS

This paper is devoted to the experimental study of the time complexity for the factorization of many digit numbers using the classical and improved Fermat method, and also the factorization algorithm based on the subtraction operation is proposed and investigated. Appropriate graphic dependencies have been constructed. It is shown that the proposed algorithm is characterized by less temporal complexity in the case where the big difference between the numbers whose product must be factorized. 0,172 0,297 0,438 1,156 1,781 4,86 6,265 12,843 26,875 32,859 103,078 214,141

646 1112,657 2775,718 11159,56 0,157 0,281 0,406 1,109 1,703 4,656 5,828 12,156 26,235 34,406 86,391 220,375 571,828 1106,469 2765,922 9080,454 0,032 0,047 0,063 0,203 0,313 0,875 1,094 2,407 4,969 6,172 18,031 42,483 116,453 269,156 437,531 937,67

References

[1] D. Venturi “Lecture Notes on Algorithmic Number Theory” New-York-Berlin: Springer-Verlag, 2009 . 217 p.

[2] S. Ishmukhametov , A. Boyko and D. Zyatdinov “ On an approach to the problem of the factorization of natural numbers” , Proceedings of High Schools. Mathematics , 2011 , pp. 15 - 22 .

[3] V. Shoup “Computational Introduction to Number Theory and Algebra” , Cambridge University Press, Sec. Edition , 2005 , 600 p.

[4] M. Kasianchuk , “ The Construction of the modified Perfect Form of Residual Classes System Using Factorization” , Radio Electronics , Computer Science, Control, 2017 , Vol. 42 , №3, pp. 53 - 59 .

[5] Ya.M. Nykolaychuk , M.M. Kasianchuk and I.Z. Yakymenko “Theoretical Foundations of the Modified Perfect Form of Residue Number System” , Cybernetics and Systems Analysis , 2016 , V. 52 , №2, pp. 219 - 223 .

[6] A.V. Agranovsky and R.A. Hadi “Practical cryptography: algorithms and their programming” , Moscow: Solon-Press, 2009 , 256 p.

[7] O.N. Vasilenko “Theoretical and numerical algorithms in cryptography”, Moscow: Center for Continuous Mathematical Education, 2003 , 326 p.

[8] N. Koblitz “ Course of Number Theory and Cryptography”, Moscow: TVP, 2001 , 260 p.

[9] R. Crandall , C. Pomerance “Prime Numbers: A Computational Perspective . Chapter 5: Exponential Factoring Algorithms ”, Springer-Verlag: New York, 2005 , pp. 2 - 6 .

[10] D. Kozaczko , S. Ivasiev , I. Yakymenko and M. Kasianchuk “Vector Module Exponential in the Remaining Classes System” , Proceedings of the 2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS' 2015 ), Warsaw, Poland, 2015 , pp. 161 - 163 .

[11] S Ishmukhametov “ Methods for the factorization of natural numbers: a tutorial” , Kazan: Kazan University, 2011 , 190 p.

[12] E.B. Makhovenko “ Theoretical and numerical methods in cryptography: Textbook” , Moscow: Helios ARV, 2006 , 320 p.

[13] RSA Challenge . URL: https://www.emc.com/emc%20plus/ rsa-labs/historical/the-rsa-challengenumbers .htm.

[14] M. Karpiński , S. Ivasiev , I. Yakymenko, M. Kasianchuk and T. Gancarczyk “ Advanced method of factorization of multi-bit numbers based on Fermat's theorem in the system of residual classes” , Proc. of 16th International Conference on Control, Automation and Systems (ICCAS-2016) , Gyeongju, Korea, V.1, October , 2016 , pp. 1484 - 1486 .