DOI: https://doi.org/10.20535/2411-1031.2018.6.2.153492

### The modified algorithm of fermat’s factorization method with base foundation of module

#### Abstract

Fermat's factorization method is considered the best at factorization the numbers *N** = p × q*, when *p* and *q* are close in value. The computational complexity of Fermat's base factorization method is defined by the number of trial *X's* when solving the equation *Y ^{2}=X^{2}-N*, and the complexity of arithmetic operations with large numbers: quadrating, addition, square root calculation. The decrease in computing complexity of this method is provided due to use of a set of bases of modules in

*Y*that in turn allows to neglect complexity of calculation square root. Allocation of primary basis of the

^{2}modb = (X^{2}-N)modbb*bb*module allows to reduce number of the trial

*X*in number times close to

*z(N, bb) =bb/bb*, where

^{*}*bb**- number of roots of an equation

*(Ymodb)*

^{2}modb=((Xmodb)^{2}*modb-Nmodb)modb*. It is shown that in the general case the primary base of the module

*bb*is the product of the degrees of prime numbers

*p*, the acceleration factor for which

*z(N, bb)*is the

*Nmodp*and exponents of

*p*. It is determined that the values of the

*Nmodp*residues influence the value of

*z(N, bb)*(for

*p*=2, the

*Nmod8*residues are used) and exponents of simple p by the value of the acceleration coefficient

*z(N, bb)*). It is offered problem formulation of search optimal

*bb*with restrictions for the memory size of PC and way of it decision. An estimate of the effectiveness proposed a modified algorithm of the Fermat's factorization method is given. It is shown that offered algorithm in the case of numbers 2

^{1024}provides a decrease in computational complexity in comparing with the basic algorithm of the Fermat’s method on average of 10

^{7}times. Use of the proposed method will allow developing more efficient, in terms of speed, hardware and software cryptanalysis tools for asymmetric cryptographic algorithms and, as a result, improve quality the evaluation of strong cryptography of asymmetric RSA cryptographic algorithms.

#### Keywords

#### Full Text:

PDF (Українська)#### References

. D. Brown, “Breaking RSA May Be As Difficult As Factoring”. [Online]. Available at: https://eprint.iacr.org/2005/380.

. D. Aggarwal, U. Maurer, “Breaking RSA Generically is Equivalent to Factoring”, in Proc. “Advances in Cryptology – EUROCRYPT”, 2009 [Online]. Available at: https://eprint.iacr.org/2008/260.

. C. Pomerance, H. Lenstra, R. Tijdeman, “Analysis and comparison of some integer factoring algorithms”, Computational methods in number theory, no. 1, pp. 89-139, 1982.

. O. Vasylenko, Teoretyko-chislovye algoritmy v kryptohrafyy. Moskva, Russia: MСNMO, 2003.

. Sh. Ishmukhametov, Methods of factoring integers. Kazan, Russia: Kazan University, 2011.

. A. Korneiko, and A. Zhilin, “Analysis of the known methods for computing the factorization of large numbers”, Collection of scientific works Institute of Modelling Problems inPower Engineering, vol. 61, pp. 3-13, 2011.

. D. Knuth, The Art of Computer Programming. Moscow, Russia: Vilyams, 2001.

. S. Vinnichuk, and Y. Maksymenko, “Mnogokratnoe prorezhivanie dlya uskoreniya metoda faktorizacii Ferma pri neravnomernyh shagah dlya neizvestnoj”, Informatics, operation and computer scienc, no. 64, pp. 13-24, 2016.

. Y. Maksymenko, “Vybir efektyvnoi bazovoy osnovy modulya pry bagatorazovomu proridzhuvanni probnykh znachen v metodi faktoryzaciyi Ferma z nerivnomirnym krokom”, Informatyka ta matematychni metody v modeliuvanni, vol. 6, no. 3, pp. 270-279, 2016.

. S. Vynnychuk, and Y. Maksymenko, “Formirovanie neravnomernyh prirashchenij dlya bazovogo osnovaniya modulya v zadache faktorizacii metodom Ferma”, Information technology and security, vol. 4, no. 2, pp. 245-254, 2016.

This work is licensed under a Creative Commons Attribution 4.0 International License.

**ISSN 2411-1031 (Print),**

**ISSN 2518-1033 (Online)**