Метод множинного квадратичного k-решета з використанням сигнальних остач при просіюванні пробних значень

С.Д. Винничук, д-р техн. наук, В.M. Місько, аспірант
Інститут проблем моделювання в енергетиці ім. Г.Е. Пухова НАН України.
(Україна, 03164, Київ, вул. Генерала Наумова, 15,
тел. +380734095726, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.; Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.

Èlektron. model. 2019, 41(2):03-22
https://doi.org/10.15407/emodel.41.02.003

АНОТАЦІЯ

Описано алгоритм методу множинного квадратичного k-решета, який є модифікацією методу квадратичного решета. У даній модифікації зпропоновано при просіюванні пробних значень виконувати попереднє їх просіювання на основі порівняння остачy yk( X ) = X2 - kN (k ≥ 1) з сигнальними остачами yk*( X ), де  yk* ( X ) — добуток перших степенів множників yk( X ). Серед пробних значень відсіюють ті, для яких log (yk( X )) < h log (yk*( X )), де дійсне число h ∈ [0,1] —це параметр, що обирається. Встановлено, що при зростанні значення N збільшується значення h, при якому досягається найменший час розрахунку. Встановлено також, що зменшення часу отримання достатньої кількості В-гладких відбувається при обмеженні для показників степенів дільників В-гладкого, які перевищують одиницю, для множини елементів загальної факторної бази, більших певного значення, визначеного за параметром kff. На основі чисельних експериментів з відносно малими числами порядку 10m при m = 20÷32 показано, що час розрахунку достатньої кількості В-гладких є функцією параметра kff. Описано кроки алгоритму методу та ідеї їх реалізації. Наведено евристичну оцінку складності запропонованого методу для ряду значень параметра pla.

КЛЮЧОВІ СЛОВА:

цілочисельна факторизація, метод квадратичного решета, множинне решето.

СПИСОК ЛІТЕРАТУРИ

1. Горбенко И.Д., Долгов В.И., Потий А.В., Федорченко В.Н. Анализ каналов уязвимости системы RSA // Безопасность информации, 1995, № 2, с. 22—26.
2. Brown Daniel R.L. Breaking RSA May Be As Difficult As Factoring. [Электронный ресурс]. Режим доступа: http://www.pgpru.com/novosti /2005/1026vzlomrsabezfaktorizaciirealennoneeffektiven. Название с экрана.
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/Quadratic_sieve. Название с экрана.
5. Silverman R.D. The multiple polynomial quadratic sieve // Math. Comp., 1987, Vol. 48 (177), p. 329—339.
6. Винничук С.Д., Місько В.М. Метод множинного k-решета цілочисельної факторизації // Електрон. моделювання, 2018, 40, № 5, c. 3—26. [Электронный ресурс]. Режим доступа: https://doi.org/10.15407/emodel.40.05.003.
7. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003, с. 328.
8. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. Казань: Казанcкий ун-т., 2011, с. 190.
9. Landquist Eric. The Quadratic Sieve Factoring Algorithm // MATH: Cryptographic Algorithms, 2001, No. 488, p. 1—11.
10. Vynnychuck S., Misko V. Acceleration analysis of the quadratic sieve method based on the online matrix solving // Mathematics and cybernetics—applied aspects, 2018, Vol. 2, No. 4 (92) p. 33—38. DOI: 10.15587/1729-4061.2018.133603.

ВИННИЧУК Степан Дмитрович, д-р техн. наук, зав. відділом Ін-ту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. В 1977 р. закінчив Чернівецький госуніверситет. Область наукових досліджень—моделі, методи і програмні засоби для аналізу систем рідини, що стискається та не стискається, теорія алгоритмів. 

МІСЬКО Віталій Миколайович, аспірант Ін-ту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. В 2013 р. закінчив Ін-т спеціального зв’язку і захисту інформації НТУУ «КПІ». Область наукових досліджень — чисельні методи та алгоритми факторизації.

Повний текст: PDF