С.Д. Винничук, д-р техн. наук, В.M. Місько, аспірант
Інститут проблем моделювання в енергетиці ім. Г.Е. Пухова НАН України
(Україна, 03164, Київ, вул. Генерала Наумова, 15,
тел. +380734095726; е-mail:
Èlektron. model. 2018, 40(3):03-26
https://doi.org/10.15407/emodel.40.05.003
АНОТАЦІЯ
Запропоновано модифікацію методу квадратичного решета (QS), в якій для пошуку В-гладких чисел використовуються поліноми X2– kN. На відміну від методів QS та множинного поліноміального квадратичного решета (MPQS) в запропонованому методі множинного квадратичного k-решета (MQkS) використовується загальна факторна база (ФБ), яка деталізується при кожному значенні k. В алгоритмі враховано, що кількість В-гладких є відносно більшою при менших значеннях чисел з інтервалу просіювання. Цей факт підтверджено даними чисельних експериментів. Описано кроки алгоритму та ідеї їх реалізації. На основі чисельних експериментів показано, що за допомогою методу MQkS можна зменшити в середньому час формування множини В-гладких порівняно з методом QS при зменшенні розміру ФБ.
КЛЮЧОВІ СЛОВА:
цілочисельна факторизація, метод квадратичного решета, множинне решето.
СПИСОК ЛІТЕРАТУРИ
1. Горбенко И.Д., Долгов В.И., Потий А.В., Федорченко В.Н. Анализ каналов уязвимости системы RSA. // Безопасность информации. 1995, № 2, с. 22—26.
2. Daniel R.L. Brown. Breaking RSA May Be As Difficult As Factoring. [Электронный ресурс].
Режим доступа: http://www.pgpru.com/novosti /2005/1026vzlomrsabezfakto-rizaciirealennoneeffektiven.— Название с экрана.
3. Kannan Balasubramanian, M. Rajakani. Algorithmic strategies for solving complex problems in cryptography. // Advances in information security, privacy, and ethics (AISPE) book series. Hershey, Pennsylvania (701 E. Chocolate Avenue, Hershey, Pennsylvania, 17033, USA) : IGI Global, 2018.
4. Quadratic sieve. [Электронный ресурс]. Режим доступа: https://en.wikipedia.org/wiki/Quadratsc_sieve.— Название с экрана.
5. Landquist E. The Quadratic Sieve Factoring Algorithm.// MATH: Cryptographic Algorithms. 2001, № 488, р. 1—11.
6. RSA numbers. [Электронный ресурс]. Режим доступа: https://en.wikipedia.org/wiki/RSA_numbers. —Название с экрана.
7. C. Pomerance. Smooth numbers and the quadratic sieve. Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, MSRI Publications, 2008, № 44, p. 69—81.
8. Vazzana A., Garth D., Erickson M.J. Introduction to number theory. Boca Raton : Chapman & Hall/CRC, 2015.
9. Guo V.Z., Banks W.D. Exponential sums, character sums, sieve methods and distribution of prime numbers. Columbia, Missouri: University of Missouri, 2017.
10. Crandall R., Pomerance C.B. Prime numbers a computational perspective. Second ed. NY: Springer, 2010.
11. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. Казань: Казанский ун-т, 2011, с. 190.
12. Sahadeo Padhye, Rajeev Anand Sahu, Vishal Saraswat. Introduction to Cryptography. Boca Raton, FL : CRC Press, 2018, р. 45.
13. Місько В.М. Прискорення методу квадратичного решета на основі використання умовно B-гладких чисел. // Зб. наук. праць. «Системні дослідження та інформаційні технології», 2018, № 1, с. 99—106.
14. Винничук С.Д, Місько В.М. Прискорення методу квадратичного решета на основі використання розширеної факторної бази та формування достатньої кількості Bгладких чисел // Зб. наук. праць. «Information technology and security», 2017, с. 67—71.
15. Vynnychuck S., Misko V. Acceleration analysis of the quadratic sieve method based on the online matrix solving. // Mathematics and cybernetics — applied aspects, 2018. DOI: 10.15587/1729-4061.2018.133603
16. Silverman R.D. The multiple polynomial quadratic sieve // Math. Comp. 1987, Vol. 48, No. 177, р. 329—339.
17. Breitenbacher D., Homoliak I., Jaros J., Hanacek P. Impact of Optimization and Parallelism on Factorization Speed of SIQS// Journal of Systemics, 2016, Vol. 4, No. 3 р. 51—58.
ВИННИЧУК Степан Дмитрович, д-р техн. наук, зав. відділом Ін-ту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. В 1977 р. закінчив Чернівецький державний університет. Область наукових досліджень—моделі, методи і програмні засоби для аналізу систем рідини, що стискається та не стискається, теорія алгоритмів.
МІСЬКО Віталій Миколайович, аспірант Ін-ту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. В 2013 р. закінчив Ін-т спеціального зв’язку і захисту інформації НТУУ «КПІ». Область наукових досліджень — чисельні методи та алгоритми факторізації.