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

Authors

  • Stepan Vynnychuk Pukhov Institute for Modelling in Energy Engineering of National academy of sciences of Ukraine, Kyiv,, Ukraine https://orcid.org/0000-0002-0605-1576
  • Yevhen Maksymenko Institute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kiev,, Ukraine https://orcid.org/0000-0003-4947-2247

DOI:

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

Keywords:

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

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.

Author Biographies

Stepan Vynnychuk, Pukhov Institute for Modelling in Energy Engineering of National academy of sciences of Ukraine, Kyiv,

doctor of technical sciences, senior researcher, head of department of modeling of energy processes and systems

Yevhen Maksymenko, Institute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kiev,

candidate of technical sciences, deputy head at the cybersecurity and application of information systems academic department

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.

Published

2018-12-30

How to Cite

Vynnychuk, S., & Maksymenko, Y. (2018). The modified algorithm of fermat’s factorization method with base foundation of module. Collection "Information Technology and Security", 6(2), 79–93. https://doi.org/10.20535/2411-1031.2018.6.2.153492

Issue

Section

СOMPUTATIONAL METHODS