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

Stepan Vynnychuk; Yevhen Maksymenko; Vadym Romanenko

doi:10.15587/1729-4061.2018.150870

Автор(и)

Stepan Vynnychuk Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164, Україна https://orcid.org/0000-0002-0605-1576
Yevhen Maksymenko Інститут спеціального зв’язку та захисту інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» вул. Верхньоключова, 4, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0003-4947-2247
Vadym Romanenko Інститут спеціального зв’язку та захисту інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» вул. Верхньоключова, 4, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0002-8668-177X

DOI:

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

Ключові слова:

факторизація, метод Ферма, обчислювальна складність, базова основа, проріджування, квадратні залишки

Анотація

Метод Ферма вважається кращим при факторизації чисел N=p×q у випадку близьких p і q. Обчислювальна складність базового алгоритму методу визначається кількістю пробних значень Х при вирішенні рівняння Y²=X²‑N, а також складністю арифметичних операцій. Для її зниження запропоновано в якості допустимих розглядати ті з пробних Х, для яких (X²-N)modbb є квадратним залишком по модулю bb, названого базовым. При використанні базової основи модуля bb число пробних Х зменшується в число раз, близьке до Z(N,bb)=bb/bb^*, де bb^* – число елементів множини Т коренів рівняння (Ymodb)²modb=((Xmodb)²-Nmodb)modb, а Z – коефіцієнт прискорення.

Визначено, що на величину Z(N,bb) впливають значения залишків Nmodp (при р=2 використовуються залишки Nmod8). Запропоновано постановку задачі пошуку bb з максимальным Z(N,bb) при обмеженях на обсяг пам’яті ЕОМ, де визначаються показники степенів простих чисел – множників bb, та спосіб її вирішення.

Для зменшення числа арифметичних операцій з великими числами попонується замість таких виконувати операції зі значеннями різниць між найближчими значеннями елементів множини Т. Тоді арифметичні операції множення і додавання з великими числами виконуються рідко. А якщо квадратний корінь з X²-N визначати тільки у випадках, коли значення
(X²-N)modb будуть квадратними залишками для багатьох різних основ модуля b, то обчислювальною складністю цієї операції можна знехтувати.

Встановлено, що тоді запропонований модифікований алгоритм методу Ферма для чисел 2¹⁰²⁴ забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 10⁷ раз

Біографії авторів

Stepan Vynnychuk, Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164

Доктор технічних наук, старший науковий співробітник, керівник відділу

Відділ моделювання енергетичних процесів і систем

Yevhen Maksymenko, Інститут спеціального зв’язку та захисту інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» вул. Верхньоключова, 4, м. Київ, Україна, 03056

Кандидат технічних наук

Vadym Romanenko, Інститут спеціального зв’язку та захисту інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» вул. Верхньоключова, 4, м. Київ, Україна, 03056

Кандидат технічних наук, завідувач кафедри

Посилання

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.