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.

Downloads

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

Vol. 6 No. 2 (2018)

Section

СOMPUTATIONAL METHODS

License

Copyright (c) 2020 Collection "Information technology and security"

Creative Commons License

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

The authors that are published in this collection, agree to the following terms:

  1. The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
     
  2. The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
     
  3. Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).