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

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

Stepan Vynnychuk, Yevhen Maksymenko, Vadym Romanenko

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

Keywords


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

References


Brown, D. (2005). Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive. Available at: https://eprint.iacr.org/2005/380.pdf

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

Pomerance, C., Lenstra, H. W., Tijdeman, R. (1982). Analysis and comparison of some integer factoring algorithms. Computational methods in number theory, 1, 89–139.

Vasilenko, O. N. (2003). Teoretiko-chislovye algoritmy v kriptografii. Moscow, 328.

Ishmuhametov, Sh. T. (2011). Metody faktorizacii natural'nyh chisel. Kazan', 213.

Korneyko, A. V., Zhilin, A. V. (2011). Analiz izvestnyh vychislitel'nyh metodov faktorizacii mnogorazryadnyh chisel. Modeliuvannia ta i formatsiyni tekhnolohiyi, 61, 3–13.

Howey, E. (2014). Primality Testing and Factorization Methods. Semantic Scholar. Available at: https://www.semanticscholar.org/paper/Primality-Testing-and-Factorization-Methods-Howey/7fd44eb2df7b39716e984d548c28f51d9dc6bbbb

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

Knuth, D. (1997). Art of Computer Programming, Vol. 2. Seminumerical Algorithms. Massachusetts, 762.

Bressoud, D. (1989). Factorization and Primality Testing. Springer-Verlag, 237. doi: https://doi.org/10.1007/978-1-4612-4544-5

Burton, D. (2012). Elementary Number Theory. TMG, 436.

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

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

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

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

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

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

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

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.

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.

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.


GOST Style Citations


Brown D. Breaking RSA may be as difficult as factoring // Cryptology ePrint Archive. 2005. URL: https://eprint.iacr.org/2005/380.pdf

Aggarwal D., Maurer U. Breaking RSA generically is equivalent to factoring // Advances in Cryptology – EUROCRYPT 2009. 2009. URL: https://eprint.iacr.org/2008/260.pdf

Pomerance C., Lenstra H. W., Tijdeman R. Analysis and comparison of some integer factoring algorithms // Computational methods in number theory. 1982. Issue 1. P. 89–139.

Vasilenko O. N. Teoretiko-chislovye algoritmy v kriptografii. Moscow, 2003. 328 p.

Ishmuhametov Sh. T. Metody faktorizacii natural'nyh chisel: ucheb. pos. Kazan', 2011. 213 p.

Korneyko A. V., Zhilin A. V. Analiz izvestnyh vychislitel'nyh metodov faktorizacii mnogorazryadnyh chisel // Modeliuvannia ta i formatsiyni tekhnolohiyi. 2011. Issue 61. P. 3–13.

Howey E. Primality Testing and Factorization Methods // Semantic Scholar. 2014. URL: https://www.semanticscholar.org/paper/Primality-Testing-and-Factorization-Methods-Howey/7fd44eb2df7b39716e984d548c28f51d9dc6bbbb

Wu M.-E., Tso R., Sun H.-M. On the improvement of Fermat factorization using a continued fraction technique // Future Generation Computer Systems. 2014. Vol. 30. P. 162–168. doi: https://doi.org/10.1016/j.future.2013.06.008 

Knuth D. Art of Computer Programming, Vol. 2. Seminumerical Algorithms. 3-rd Edition. Massachusetts, 1997. 762 p.

Bressoud D. Factorization and Primality Testing. Springer-Verlag, 1989. 237 p. doi: https://doi.org/10.1007/978-1-4612-4544-5 

Burton D. Elementary Number Theory. 7-th Edition. TMG, 2012. 436 p.

Somsuk K., Tientanopajai K. An Improvement of Fermat’s Factorization by Considering the Last m Digits of Modulus to Decrease Computation Time // International Journal of Network Security. 2017. Vol. 19, Issue 1. P. 99–111. doi: http://doi.org/10.6633/IJNS.201701.19(1).11

Somsuk K., Kasemvilas S. MFFV2 and MNQSV2: Improved Factorization Algorithms // 2013 International Conference on Information Science and Applications (ICISA). 2013. doi: https://doi.org/10.1109/icisa.2013.6579415 

Somsuk K., Kasemvilas S. MFFV3: An Improved Integer Factorization Algorithm to Increase Computation Speed // Advanced Materials Research. 2014. Vol. 931-932. P. 1432–1436. doi: https://doi.org/10.4028/www.scientific.net/amr.931-932.1432 

Usman M., Bajwa Z., Afza M. New Factoring Algorithm: Prime Factoring Algorithm // International Journal of Engineering and Management Research. 2015. Vol. 5, Issue 1. P. 75–77. URL: https://pdfs.semanticscholar.org///10d5/4bf2a4b8f46a99effa195077024d82212683.pdf

Somsuk K., Kasemvilas S. Possible Prime Modified Fermat Factorization: New Improved Integer Factorization to Decrease Computation Time for Breaking RSA // Advances in Intelligent Systems and Computing. 2014. P. 325–334. doi: https://doi.org/10.1007/978-3-319-06538-0_32 

Somsuk K. A new modified integer factorization algorithm using integer modulo 20’s technique // International Computer Science and Engineering Conference (ICSEC’14). 2014. P. 312–316. URL: https://www.semanticscholar.org/paper/A-new-modified-integer-factorization-algorithm-20's-Somsuk/d70a527c0a4a7c671c814aad6de140dcbabe4445

Wu M.-E., Tso R., Sun H.-M. On the Improvement of Fermat Factorization // Lecture Notes in Computer Science. 2012. P. 380–391. doi: https://doi.org/10.1007/978-3-642-34601-9_29 

Vinnichuk S. D., Maksimenko E. V. Mnogokratnoe prorezhivanie dlya uskoreniya metoda faktorizacii Ferma pri neravnomernyh shagah dlya neizvestnoy // Visnyk NTUU “KPI”. Informatyka, upravlinnia ta obchysliuvalna. 2016. Issue 64. P. 13–24.

Maksymenko Ye. 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. 2016. Vol. 6, Issue 3. P. 270–279.

Vynnychuk S., Maksymenko Y. Formation of non-uniformity increment for the basic module base in the problem of fermat’s factorization method // Information Technology and Security. 2016. Vol. 4, Issue 2. P. 244–254.







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.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061