Application of the basic module's foundation for factorization of big numbers by the Fеrmаt method

Authors

  • Stepan Vynnychuk Pukhov Institute for Modelling in Energy Engineering National Academy of Sciences of Ukraine Henerala Naumova str., 15, Kyiv, Ukraine, 03164, Ukraine https://orcid.org/0000-0002-0605-1576
  • Yevhen Maksymenko Institute of Special Communication and Information Security National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" Verhnyoklyuchova str., 4, Kyiv, Ukraine, 03056, Ukraine https://orcid.org/0000-0003-4947-2247
  • Vadym Romanenko Institute of Special Communication and Information Security National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" Verhnyoklyuchova str., 4, Kyiv, Ukraine, 03056, Ukraine https://orcid.org/0000-0002-8668-177X

DOI:

https://doi.org/10.15587/1729-4061.2018.150870

Keywords:

factorization, Fermat method, computational complexity, basic foundation, thinning, quadratic residues

Abstract

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 Y2=X2‑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 (X2–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*, where bb* is the number of elements of set Т of the roots of equation (Ymodb)2modb=((Xmodb)2–Nmodb)modb, and Z is the acceleration coefficient.

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.

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 X2–N only in cases, where the values of (X2–N)modb will be quadratic residues for many foundations of module b, other than bb, the computational complexity of this operation can be neglected.

It was established that the proposed modified algorithm of the Fermat method for numbers 21024 ensures a decrease in computational complexity compared to the basic algorithm on average by 107 times

Author Biographies

Stepan Vynnychuk, Pukhov Institute for Modelling in Energy Engineering National Academy of Sciences of Ukraine Henerala Naumova str., 15, Kyiv, Ukraine, 03164

Doctor of Technical Sciences, Senior Researcher, Head of Department

Department of modeling of energy processes and systems

Yevhen Maksymenko, Institute of Special Communication and Information Security National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" Verhnyoklyuchova str., 4, Kyiv, Ukraine, 03056

PhD

Vadym Romanenko, Institute of Special Communication and Information Security National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" Verhnyoklyuchova str., 4, Kyiv, Ukraine, 03056

PhD, Head of Department

References

  1. Brown, D. (2005). Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive. Available at: https://eprint.iacr.org/2005/380.pdf
  2. Aggarwal, D., Maurer, U. (2009). Breaking RSA generically is equivalent to factoring. Advances in Cryptology – EUROCRYPT 2009. Available at: https://eprint.iacr.org/2008/260.pdf
  3. Pomerance, C., Lenstra, H. W., Tijdeman, R. (1982). Analysis and comparison of some integer factoring algorithms. Computational methods in number theory, 1, 89–139.
  4. Vasilenko, O. N. (2003). Teoretiko-chislovye algoritmy v kriptografii. Moscow, 328.
  5. Ishmuhametov, Sh. T. (2011). Metody faktorizacii natural'nyh chisel. Kazan', 213.
  6. Korneyko, A. V., Zhilin, A. V. (2011). Analiz izvestnyh vychislitel'nyh metodov faktorizacii mnogorazryadnyh chisel. Modeliuvannia ta i formatsiyni tekhnolohiyi, 61, 3–13.
  7. Howey, E. (2014). Primality Testing and Factorization Methods. Semantic Scholar. Available at: https://www.semanticscholar.org/paper/Primality-Testing-and-Factorization-Methods-Howey/7fd44eb2df7b39716e984d548c28f51d9dc6bbbb
  8. Wu, M.-E., Tso, R., Sun, H.-M. (2014). On the improvement of Fermat factorization using a continued fraction technique. Future Generation Computer Systems, 30, 162–168. doi: https://doi.org/10.1016/j.future.2013.06.008
  9. Knuth, D. (1997). Art of Computer Programming, Vol. 2. Seminumerical Algorithms. Massachusetts, 762.
  10. Bressoud, D. (1989). Factorization and Primality Testing. Springer-Verlag, 237. doi: https://doi.org/10.1007/978-1-4612-4544-5
  11. Burton, D. (2012). Elementary Number Theory. TMG, 436.
  12. Somsuk, K., Tientanopajai, K. (2017). An Improvement of Fermat’s Factorization by Considering the Last m Digits of Modulus to Decrease Computation Time. International Journal of Network Security, 19 (1), 99–111. doi: http://doi.org/10.6633/IJNS.201701.19(1).11
  13. Somsuk, K., Kasemvilas, S. (2013). MFFV2 and MNQSV2: Improved Factorization Algorithms. 2013 International Conference on Information Science and Applications (ICISA). doi: https://doi.org/10.1109/icisa.2013.6579415
  14. Somsuk, K., Kasemvilas, S. (2014). MFFV3: An Improved Integer Factorization Algorithm to Increase Computation Speed. Advanced Materials Research, 931-932, 1432–1436. doi: https://doi.org/10.4028/www.scientific.net/amr.931-932.1432
  15. Usman, M., Bajwa, Z., Afza, M. (2015). New Factoring Algorithm: Prime Factoring Algorithm. International Journal of Engineering and Management Research, 5 (1), 75–77. Available at: https://pdfs.semanticscholar.org///10d5/4bf2a4b8f46a99effa195077024d82212683.pdf
  16. Somsuk, K., Kasemvilas, S. (2014). Possible Prime Modified Fermat Factorization: New Improved Integer Factorization to Decrease Computation Time for Breaking RSA. Advances in Intelligent Systems and Computing, 325–334. doi: https://doi.org/10.1007/978-3-319-06538-0_32
  17. Somsuk, K. (2014). A new modified integer factorization algorithm using integer modulo 20’s technique. International Computer Science and Engineering Conference (ICSEC’14), 312–316. Available at: https://www.semanticscholar.org/paper/A-new-modified-integer-factorization-algorithm-20's-Somsuk/d70a527c0a4a7c671c814aad6de140dcbabe4445
  18. Wu, M.-E., Tso, R., Sun, H.-M. (2012). On the Improvement of Fermat Factorization. Lecture Notes in Computer Science, 380–391. doi: https://doi.org/10.1007/978-3-642-34601-9_29
  19. Vinnichuk, S. D., Maksimenko, E. V. (2016). Mnogokratnoe prorezhivanie dlya uskoreniya metoda faktorizacii Ferma pri neravnomernyh shagah dlya neizvestnoy. Visnyk NTUU “KPI”. Informatyka, upravlinnia ta obchysliuvalna, 64, 13–24.
  20. Maksymenko, Ye. (2016). Selection of effective basic basis of module with multiple thinning trial value in the factorization fermat's method with irregular pitch. Informatyka ta matematychni metody v modeliuvanni, 6 (3), 270–279.
  21. Vynnychuk, S., Maksymenko, Y. (2016). Formation of non-uniformity increment for the basic module base in the problem of fermat’s factorization method. Information Technology and Security, 4 (2), 244–254.

Downloads

Published

2018-12-13

How to Cite

Vynnychuk, S., Maksymenko, Y., & Romanenko, V. (2018). Application of the basic module’s foundation for factorization of big numbers by the Fеrmаt method. Eastern-European Journal of Enterprise Technologies, 6(4 (96), 14–23. https://doi.org/10.15587/1729-4061.2018.150870

Issue

Vol. 6 No. 4 (96) (2018): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2018 Stepan Vynnychuk, Yevhen Maksymenko, Vadym Romanenko

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.