ПРИМЕНЕНИЕ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ ФАКТОРИЗАЦИИ БОЛЬШИХ ЧИСЕЛ

Юрий Л. Зачёсов, Вера Ю. Ягунова, Игорь М. Ядыкин

Аннотация


Факторизация больших чисел остаётся важной областью исследований в криптографии. По мере развития алгоритмов и вычислительных мощностей, размеры ключей и криптографические методы должны постоянно адаптироваться, чтобы обеспечивать надёжную защиту информации. Известны десятки различных методов факторизации, все они имеют большую вычислительную сложность при большом значении модуля факторизации, как правило, лучшие методы, имеют большую математическую сложность. В настоящее время лучшим субэкспоненциальным алгоритмом факторизации семипримарных чисел считается метод решета числового поля. Актуальной остаётся задача построения более эффективного, полиномиально разрешимого алгоритма факторизации. В данной работе для построения алгоритма используется методология динамических систем (ДС), позволяющая решать задачу поэтапно в определённой последовательности. Разработан алгоритм, использующий аппарат целочисленного программирования, с целью создания полиномиального алгоритма факторизации больших семипримарных чисел. В работе обосновывается возможность создания такой системы на основе полиномиального алгоритма получения инвариантных систем начальных многочленов. Результатом работы алгоритмов ДС будет система приведённых многочленов, взаимно-однозначно соответствующих начальным. Независимо от битового размера модуля факторизации, алгоритм имеет полиномиальную трудоёмкость. Дополнительным результатом является целочисленность корней выходной алгебраической структуры, что характерно для методов целочисленного программирования. Новый подход предполагает замену решения систем уравнений геометрическим поиском. Теоретические исследования подтверждены проведенными экспериментальными расчётами для различных типов входных данных.

Ключевые слова


целочисленное программирование, алгебраические инварианты, алгоритм факторизации, динамическая система

Полный текст:

PDF

Литература


1. Pollard, J.M. (1974). Theorems on Factorization and Primarily Testing. Mathematical Proceeding of the Cambridge Philosophical Society. 76(3), 521-528. DOI: http://doi.org/10.1017/S0305004100049252.
2. Gordon, W.J. (1983). An Operator Calculus for Surface and Volume Modeling. IEEE Computer Graphics and Applications. 3(7), 18-22. DOI: http://doi.org/10.1109/MCG.1983.263268.
3. Silverman, R.D. (1987). The Multiple Polynomial Quadratic Sieve. Mathematics of Computation, 48(177),
329-339. DOI: http://doi.org/10.1090/S0025-5718-1987-0866119-8.
4. Lenstra, A.K., & Lenstra, H.W. (1993). The Development of the Number Field Sieve. Springer. DOI: https://doi.org/10.1007/BFb0091534.
5. Schnorr, C.P.: Factoring Integer and Computing Discrete Logarithms via Diophantine Approximation. In: Davies, D.W. (ed) Advances in Cryptology – EUROCRYPT’91. Lecture Notes in Computer Science, v. 547. Springer, Berlin, Heidelberg. DOI: http://doi.org/10.1007/3-540-46416-6_24.
6. Зачёсов, Ю., Ядыкин, И. (2024). Алгоритм получения инвариантов. Безопасность информационных технологий, 31(2), 65-80. DOI: http://dx.doi.org/10.26583/bit.2024.2.04.
Zachesov, Y., Yadykin, I. (2024). Algorithm obtaining invariants. IT Security (Russia), 31(2), 65-80. DOI: http://doi.org/10.26583/bit.2024.2.04 (in Russian).
7. Reddy K.S.K., Rao D.A.K., Kumarraja A. and Varma B.R.K. Implementation of Integer Linear Programming and Exhaustive Search algorithms for optimal PMU placement under various conditions. IEEE Power, Communication and Information Technology Conference (PCITC), Bhubaneswar, India, 2015, pp. 850-855. DOI: http://doi.org/10.1109/PCITC.2015.7438114.
8. Волков И.К., Загоруйко Е.А. Исследование операций. Москва. Изд-во МГТУ им. Н.Э. Баумана. 2004. – 438 c. ISBN: 5-7038-1518-5. EDN: QJLJOP.
Volkov I.K., Zagoruyka E.А. Operation reseach. Moscow. Publishing house MGTU names N.A. Bauman. 2004. 436 p. ISBN: 5-7038-1518-5. EDN: QJLJOP (in Russian).
9. Карманов B.Г. Математическое программирование. 6-е издание. Москва: Физматлит, 2008. – 264 с. ISBN 978-5-9221-0983-3. EDN: MVANGH.
Karmanov V.G. Mathematical Programming: Textbook 6 editions. Moscow: Fizmatlit, 2008. 264 p. ISBN 978-5-9221-0983-3. EDN: MVANGH (in Russian).
10. Ядыкин И.М. Устройство для решения задач целочисленного линейного программирования. НИЯУ МИФИ. Патент RU 2518998 C1, опубликовано 10.06.2014, бюл. №16. EDN: YPWGRU.
Yadykin I.M. Device for solving integer programming problem. National Research Nuclear University MEPhI, patent RU 2518998 C1, published 10.06.2014, bill. № 16. EDN: YPWGRU (in Russian).
11. Зачёсов Ю.Л., Ядыкин И.М. Применение китайской теоремы об остатках для факторизации целых чисел. Кибернетика и информационная безопасность "КИБ-2024": Сборник научных трудов Второй Всероссийской научно-технической конференции, Москва, 22–23 октября 2024 года. Москва: Национальный исследовательский ядерный университет "МИФИ", с. 80-81. EDN: LXBHHW.
Zachesov, Yurii L.; Yadykin, Igor M. Application of the Chinese Residue Theorem for Factorization of Integers. In: Cybernetics and Information Security "KIB-2024": Proceedings of the Second All Russian Scientific and Technical Conference, Moscow, October 22–23, 2024. Moscow: National Research Nuclear University "MEPhI", pp. 80-81. EDN: LXBHHW (in Russian).
12. Coppersmith, D. (1996). Finding a Small Root of a Univariate Modular Equation. In: Maurer, U. (eds) Advances in Cryptology – EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, v. 1070. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/3-540-68339-9_14.
13. Зачёсов Ю.Л., Салихов Н.П. О методе решения полиномиального сравнения P(x)≡0(mod N). Обозрение прикладной и промышленной математики. 2008, т. 15, № 5, с. 769-784. EDN: KAXSIZ.
Zachesov, Yurii L.; Salixov N.H. A method for solving of polynomial CONGRU ENCE P(x)≡0(mod N). Reviews of applied industrial mathematics. 2008, v. 15, no. 5. pp. 769-784. EDN: KAXSIZ (in Russian).
14. Привалов И.И. Аналитическая геометрия: учебник для вузов. Москва: Издательство Юрайт, 2025. – 233 с. ISBN 978-5-534-01262-0.URL: https://urait.ru/bcode/598531 (дата обращения: 21.03.2026).
Privalov I.I., Analytical geometry: Textbook for universities. Moscow: Yurayt Publishing House, 2025. 233 p. ISBN 978-5-534-01262-0. URL: https://urait.ru/bcode/561161 (accessed: 21.03.2026) (in Russian).
15. Шарый С.П. Конечномерный интервальный анализ. Институт вычислительных технологий СО РАН. Новосибирск: Изд-во «XYZ», 2026. – 676 c. URL: http://www.nsc.ru/interval/Library/InteBooks/SharyBook. (дата обращения: 21.03.2026).
Shariy S.P. Final Interval analyses. Institute of Computational Technologies SO RAH. Publishing House "XYZ". 2026. 676 p. URL: http://www.nsc.ru/interval/Library/InteBooks/SharyBook (accessed: 21.03.2026) (in Russian).
16. Зачёсов Ю.Л., Ядыкин И.М. Чередование чётности сумм младших разрядов у простых чисел. Кибернетика и информационная безопасность "КИБ-2024": Сборник научных трудов Второй Всероссийской научно-технической конференции, Москва, 22–23 октября 2024 года. Москва: Национальный исследовательский ядерный университет "МИФИ", c. 78-79. EDN: IPUTKI.
Zachesov, Yu.L. and Yadykin, I.M. (2024). Alternation of Parity of Low Order Bit Sums for Prime Numbers. In: Cybernetics and Information Security "KIB-2024": Proceedings of the Second All Russian Scientific and Technical Conference, Moscow, October 22–23, 2024. Moscow: National Research Nuclear University "MEPhI", pp. 78-79. EDN: IPUTKI (in Russian).




DOI: http://dx.doi.org/10.26583/bit.2026.3.06

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.