МЕТОД МНОЖЕСТВЕННОГО КВАДРАТИЧНОГО k-РЕШЕТА С ИСПОЛЬЗОВАНИЕМ СИГНАЛЬНЫХ ОСТАТКОВ ПРИ ПРОСЕИВАНИИ ПРОБНЫХ ЗНАЧЕНИЙ

C.Д. Винничук, В.Н. Мисько

È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