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

Stepan Vynnychuk, Yevhen Maksymenko

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 Y2=X2-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 Y2modb = (X2-N)modbb that in turn allows to neglect complexity of calculation square root. Allocation of primary basis of the 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)2modb=((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 21024 provides a decrease in computational complexity in comparing with the basic algorithm of the Fermat’s method on average of 107 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


Factorization; Fermat method; thinning; base foundation; computational complexity.

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.




ISSN 2411-1031 (Print), ISSN 2518-1033 (Online)