=Paper=
{{Paper
|id=Vol-2300/Paper56
|storemode=property
|title=The Method of Factorizing Multi-Digit Numbers Based on the Operation of Adding Odd Numbers
|pdfUrl=https://ceur-ws.org/Vol-2300/Paper56.pdf
|volume=Vol-2300
|authors=Mykhailo Kasianchuk,Igor Yakymenko,Stepan Ivasiev,Ruslan Shevchuk,Lidiya Tymoshenko
|dblpUrl=https://dblp.org/rec/conf/acit4/KasianchukYIST18
}}
==The Method of Factorizing Multi-Digit Numbers Based on the Operation of Adding Odd Numbers==
https://ceur-ws.org/Vol-2300/Paper56.pdf
232
The Method of Factorizing Multi-Digit Numbers Based
on the Operation of Adding Odd Numbers
Mykhailo Kasianchuk1, Igor Yakymenko1, Stepan Ivasiev2, Ruslan Shevchuk3, Lidiya
Tymoshenko4
1. Department of Computer Engineering, Ternopil National Economic University, UKRAINE, Ternopil, 8 Chekhova str., email:
kasyanchuk@ukr.net, iyakymenko@ukr.net,
2. Department of Cyber Security, Ternopil National Economic University, UKRAINE, Ternopil, 8 Chekhova str.,
email:stepan.ivasiev@gmail.com
3. Department of Computer Science, Ternopil National Economic University, UKRAINE, Ternopil, 8 Chekhova str., email: rsh@tneu.edu.ua
4. Department of Computer Science and Information Systems Management, Odesa National Polytechnic University, UKRAINE, Odesa, 1
Shevchenko Str., e-mail: lmt0902@gmail.com
Abstract: The method for factorizing multi-digit number. In connection with this, it is necessary to develop
numbers based on the addition of odd numbers is other approaches to solving the problem of factorization of
developed in this article. The temporal characteristics of integers.
software implementations of the proposed method, the
classical Fermat method and its improvement are II. FERMAT'S FACTORIZATION METHOD
experimentally investigated. It is revealed that the Fermat's method is the most widely used method [11],
proposed algorithm, whose time reduction is linear, has which is based on the search for pairs of natural numbers А
an advantage over the other two with a large difference and В, for which equality n=A2-B2 is performed, where n=p⋅q
between the multipliers that are factorized. Other is known integer, which is the product of two unknown
dependencies are declining parabolic. primes p and q, which should be found.
Keywords: factorization, Fermat method, addition,
multi-digit numbers, time complexity.
[ ]
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
I. INTRODUCTION a number, for example В2.
The factorization of a natural number or its Then, respectively, А2=(m+x)2 and the desired
decomposition into simple multipliers belongs to the main decomposition will be n=p⋅q= А2-В2=(А-В)(А+В).
problems of the modern theory of numbers [1-3], various The most computable complex operations in this case are
forms of the system of residual classes [4, 5] and plays an elevation to a square and the search for a square root. In [14],
important role in cryptographic information security systems an improved Fermat’s factorization method is proposed,
[6-8]. As a rule, large-scale computing and time resources are where the condition is used that squares of integers can be
required for the expansion of the multiplicity of the number represented as a sum of odd numbers, the number of which is
obtained as a result of the product of two large prime equal to this number:
numbers [9]. s
This circumstance is used in cryptographic algorithms as s 2 = ∑ (2i − 1)
i =1 . (1)
protection against potential hacking attempts: for the creation
and multiplication of two prime numbers of large bits, it does Therefore, having found m та f 1 (x)=f(x) when х=1, the
not require significant costs [10], and their factorization is a following steps occur according to the expression
long and laborious process. Despite the considerable efforts f i =f i-1 +2(m+i)-1, where і=2, 3, 4, … as long as f i will not be a
of scientists in this direction, to date, there are no quantum full square of a certain number.
algorithms for factorizing multi-digit numbers, which allow The decomposition for multipliers will be determined by
executing the timetable for the multipliers at a practical time. this expression: n=(m+i-f i )( m+i+f i ).
But the proof that there is no solution to this problem in Table 1 provides an example of factorization using the
classical and improved Fermat’s method for n=4717
[ ]
polynomial time is also absent [11].
Particular interest to the factorization problem was the ( m1 = 4717 = 68 ).
emergence of cryptographic algorithm encryption RSA, TABLE 1. EXAMPLE OF THE FACTORIZATION OF THE NUMBER
which uses its computational complexity [12]. 4717 USING CLASSICAL AND IMPROVED FERMAT’S METHOD
The decomposition of numbers containing in a binary
х m+x f(x), classical f(x), improved method
record up to 768 bits inclusive was obtained for polynomial
method
time by the modern methods (in particular, the general
1 62 692-4717=44 622-4717=44
method of the numerical field sieve) [13]. However, further 2
2 63 70 -4717=183 44+139=183
increase in the dimension significantly increases the
complexity of the scheduling operation of a composite 3 64 712-4717=324=182 183+141=324=182
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
233
Thus the decomposition of the number 4717 on simple for n=53⋅89=4717 ( m1 = [ 4717 ] = 68 ).
multipliers is obtained:
4717=712-182=(71+18)(71-18)=89⋅53.
It should be noted that the number of iterations in both begin
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 n
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.
q = n − n
2
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 r1=1
for the experimental study, as well as an experimental study r2 = n ⋅ 2 + 1
of the time characteristics of the software implementation of
the Fermat’s method, its modification and the proposed
q= q+r2
algorithm.
III. DESCRIPTION OF THE PROPOSED
FACTORIZATION ALGORITHM r2= r2+2
The property (1) is also used in the proposed algorithm,
the parameters m 1 =m and f 11 =f 1 are calculated similarly to
the previous case. Then the sequence of operations f 1і =f 1 і-1 -r 1 q = q - r1
і-1 , r 11 =1, r 1 і-1 =2i-3=r 1 і-2 +2, i=2, 3, … are performed until
the condition for some і is not fulfilled:
r1= r1+2
f 1і -r 1і ≤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.
q- r1> 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)
q=0
fj+1 1= fjі+2mj+1-rjі≤0, rj i+1=rjі+2, if fjі-rjі<0. (4)
Under the condition fjі-rjі=0, the desired quantities
А=(m+j) and B = (m + j ) − n are determined which will be
2
a positive integer, the desired quantity, which will be a (r2-1)/2-(r1-1)/2
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. end
Fig. 1 shows a block diagram of the developed algorithm,
and in the Table 2, the corresponding example is presented Fig. 1. Block diagram of the developed algorithm
TABLE 2. THE EXAMPLE OF FACTORIZATION OF THE NUMBER 4717 BY THE PROPOSED ALGORITHM
i j=1, m1=68 j=2, m2=69 j=3, m3=70
f1i r1i f2i r2i f3i r3i
1 692-4717= 44 1 8+139-13= 134 15 14+141-27= 128 29
2 44-1=43 3 134-15= 119 17 128-29= 99 31
3 43-3=40 5 119-17=102 19 99-31=68 33
4 40-5=35 7 102-19=83 21 68-33= 35 35
5 35-7=28 9 83-21=62 23 35-35=0
6 28-9=19 11 62-23=39 25
7 19-11= 8<13 13 39-25=14<27 27
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
234
Consequently, the decomposition of the number 4717 into All calculations were carried out on a portable computer
simple multipliers are carried out in this way: Lenovo B50-70 with processor Intel Pentium 3558U (1.7
B = (68 + 3)2 − 4717 = 18 , 4717=712-182=(71+18)⋅ ⋅(71- GHz). The amount of RAM in the device was 4 GB. When
designing the computing software, a high level programming
18)=89⋅53. This procedure is performed without the use of a language C ++ was selected, which allows you to transform
computationally cumbersome operation extracting the square the codes into different architectures and operating systems.
root. Additionally, addition and subtraction are performed All graphics are descending character, indicating a
over smaller numbers than in the two previous methods, decrease in the factorization time with a decrease in the
although the number of these operations is greater. difference between the multipliers, whose product is
IV. EXPERIMENTAL STUDY OF TIME factorized. The proposed algorithm, whose time reduction is
linear, has an advantage over the other two at small values of
CHARACTERISTICS OF FACTORIZATION METHODS q. With increasing q the least time is characterized by an
The multiplier р was chosen to be fixed and equal to the improved Fermat’s algorithm.
largest prime number of a certain bit rate for the experimental Further growth of q leads to the fact that the proposed
study of the factorization of the number n=p⋅q. algorithm uses the most time compared to the other two. It
Then, a number of prime numbers of the same digit are should be noted that with increasing the bit rate number of
determined that of p, of which 1000 values for the number q the point of intersection of the straight line with the curves
were selected uniformly in the order of growth. obtained by using the Fermat’s method, are shifted to the left
After multiplying p by q, the timer fixed the factorization on the graphs.
time for each of the 1000 received products. Figure 4 depicts the graphs of the dependence of the
The time characteristics of the software implementation of average factorization time of three methods on the bit rate
the classical (curve 1) and improved (curve 2) Fermat’s number for 1000 values selected by the above-described
methods, as well as the proposed algorithm (curve 3) are method. It can be seen that all graphs grow in parabolic law
presented in Figures 2 and 3 for the bit rates 30 with increasing bit rate. The least average factorization time
(р=1073741789) and 32 (р=4294967291) bits respectively. is characterized by an improved Fermat’s algorithm, and the
largest one is classical.
Fig. 2. Time characteristics of software implementation of
factorization methods for multipliers with bit rate 30 bits (j –
number in the sample)
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.
Fig. 3. Time characteristics of software implementation of
factorization methods for multipliers with bit rate 32 bits (j –
number in the sample)
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic
235
TABLE 3. INVESTIGATION OF THE TIME CHARACTERISTICS
р q p ⋅q t1, s t2, s t3, s
3571 99991 357067861 0,031 0,031 0,016
3571 323789 1156250519 0,172 0,157 0,032
3571 523771 1870386241 0,297 0,281 0,047
3571 723791 2584657661 0,438 0,406 0,063
3571 1913803 6834190513 1,156 1,109 0,203
3571 2913803 10405190513 1,781 1,703 0,313
3571 7913809 28260211939 4,86 4,656 0,875
3571 9913807 35402204797 6,265 5,828 1,094
3571 19191383 68532428693 12,843 12,156 2,407
3571 39192331 139955814001 26,875 26,235 4,969
3571 49392341 176380049711 32,859 34,406 6,172
3571 139392347 497770071137 103,078 86,391 18,031
3571 337392373 1204828163983 214,141 220,375 42,483
3571 931392317 3326001964007 646 571,828 116,453
3571 1931392319 6897001971149 1112,657 1106,469 269,156
3571 2971215073 10610209025683 2775,718 2765,922 437,531
3571 6712170737 23969161701827 11159,56 9080,454 937,67
V. CONCLUSIONS [7] O.N. Vasilenko “Theoretical and numerical algorithms
This paper is devoted to the experimental study of the in cryptography”, Moscow: Center for Continuous
time complexity for the factorization of many digit numbers Mathematical Education, 2003, 326 p.
using the classical and improved Fermat method, and also the [8] N. Koblitz “Course of Number Theory and
factorization algorithm based on the subtraction operation is Cryptography”, Moscow: TVP, 2001, 260 p.
proposed and investigated. Appropriate graphic dependencies [9] R. Crandall, C. Pomerance “Prime Numbers: A
have been constructed. It is shown that the proposed Computational Perspective. Chapter 5: Exponential
algorithm is characterized by less temporal complexity in the Factoring Algorithms”, Springer-Verlag: New York,
case where the big difference between the numbers whose 2005, pp. 2-6.
product must be factorized. [10] D. Kozaczko, S. Ivasiev, I. Yakymenko and M.
Kasianchuk “Vector Module Exponential in the
REFERENCES Remaining Classes System”, Proceedings of the 2015
[1] D. Venturi “Lecture Notes on Algorithmic Number IEEE 8th International Conference on Intelligent Data
Theory” New-York-Berlin: Springer-Verlag, 2009. 217 Acquisition and Advanced Computing Systems:
p. Technology and Applications (IDAACS’2015), Warsaw,
[2] S. Ishmukhametov, A. Boyko and D. Zyatdinov “On an Poland, 2015, pp. 161-163.
approach to the problem of the factorization of natural [11] S Ishmukhametov “Methods for the factorization of
numbers”, Proceedings of High Schools. Mathematics, natural numbers: a tutorial”, Kazan: Kazan University,
2011, pp. 15–22. 2011, 190 p.
[3] V. Shoup “Computational Introduction to Number [12] E.B. Makhovenko “Theoretical and numerical methods
Theory and Algebra”, Cambridge University Press, in cryptography: Textbook”, Moscow: Helios ARV,
Sec.Edition, 2005, 600 p. 2006, 320 p.
[4] M. Kasianchuk, “The Construction of the modified [13] RSA Challenge. URL: https://www.emc.com/emc-
Perfect Form of Residual Classes System Using %20plus/rsa-labs/historical/the-rsa-challenge-
Factorization”, Radio Electronics, Computer Science, numbers.htm.
Control, 2017, Vol.42, №3, pp. 53-59. [14] M. Karpiński, S. Ivasiev, I. Yakymenko, M. Kasianchuk
[5] Ya.M. Nykolaychuk, M.M. Kasianchuk and and T. Gancarczyk “Advanced method of factorization
I.Z. Yakymenko “Theoretical Foundations of the of multi-bit numbers based on Fermat's theorem in the
Modified Perfect Form of Residue Number System”, system of residual classes”, Proc. of 16th International
Cybernetics and Systems Analysis, 2016, V.52, №2, pp. Conference on Control, Automation and Systems
219-223. (ICCAS–2016), Gyeongju, Korea, V.1, October, 2016,
[6] A.V. Agranovsky and R.A. Hadi “Practical pp. 1484–1486.
cryptography: algorithms and their programming”,
Moscow: Solon-Press, 2009, 256 p.
ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic