Application of the basic module's foundation for factorization of big numbers by the Fеrmаt method
Journal Title: Восточно-Европейский журнал передовых технологий - Year 2018, Vol 6, Issue 4
Abstract
<p>The Fermat method is considered to be the best for factorization of numbers N=p×q in case of close p and q. Computational complexity of the basic algorithm of the method is determined by the number of check values of X when solving equation Y<sup>2</sup>=X<sup>2</sup>‑N, as well as by complexity of the arithmetic operations. To reduce it, it is proposed to consider admissible those of test values X, for which (X<sup>2</sup>–N)modbb is quadratic residue modulo bb, called basic. Application of basic foundation of module bb makes it possible to decrease the number of check X by the number of times, close to Z=bb/bb<sup>*</sup>, where bb<sup>* </sup>is the number of elements of set Т of the roots of equation (Ymodb)<sup>2</sup>modb=((Xmodb)<sup>2</sup>–Nmodb)modb, and Z is the acceleration coefficient.</p><p>It was determined that magnitude Z(N, bb) is affected by the value of residues Nmodp (at p=2, Nmod8 residues are used). The statement of the problem of finding bb with a maximum Z(N, bb) at restrictions for the amount of memory of the computer, where exponents of prime numbers – multipliers bb – are determined, and the method of its solution were proposed.</p><p>To decrease the number of arithmetic operations with big numbers, it was proposed that instead of them to perform the operations with the values of differences between the nearest values of elements T. Then arithmetic operations of multiplication and addition with big numbers are performed only in rare cases. And if we derive the square root of X<sup>2</sup>–N only in cases, where the values of (X<sup>2</sup>–N)modb will be quadratic residues for many foundations of module b, other than bb, the computational complexity of this operation can be neglected.</p>It was established that the proposed modified algorithm of the Fermat method for numbers 2<sup>1024</sup> ensures a decrease in computational complexity compared to the basic algorithm on average by 10<sup>7</sup> times
Authors and Affiliations
Stepan Vynnychuk, Yevhen Maksymenko, Vadym Romanenko
Keywords
Related Articles
- EP ID EP528266
- DOI 10.15587/1729-4061.2018.150870
- Views 90
- Downloads 0
Identification of heat exchange process in the evaporators of absorption refrigerating units under conditions of uncertainty
<p>Analysis of the evaporator of the absorption refrigerating secondary condensation unit of ammonia production was performed. The need to minimize the temperature mode of operation of the evaporator, which provides for...
The influence of the blade feather constructional inhomogeneity on the turbine cooling blades stress-strain state
<p>The problem of gas turbine engines inhomogeneous rotor blades stress-strain state has been studied. For this purpose, the new, more correct mathematical model, based on the special three-dimensional curvilinear finite...
Electric heaters based on nanomodified paraffin with selfinstalling heat contact for antiicing systems of aerospace crafts
Improved effectiveness of ice protection systems of aerospace crafts can be achieved with the development of more effective heaters. Self-regulating electric heaters based on positive or negative temperature coefficient...
Influence of the CaO-containing modifiers on the properties of alkaline alyumosilicate binders
<p>The basis for ensuring the resistance of artificial stone based on alkaline aluminosilicate binders to variable environmental conditions is the formation of zeolite- and mica-like hydrate neo-formations.</p><p>It is p...
Development of praxeological principles to model/study heat generation and heat consumption processes in the engine of rapid internal combustion
<p>We consider a technology for modeling/studying phenomena of heat formation, heat transfer, heat utilization in the engine of rapid internal combustion, underlying which are the principles of praxeology. It is recogniz...