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

Èlektron. model. 2018, 40(5):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 р. закінчив Ін-т спеціального зв’язку і захисту інформації НТУУ «КПІ». Область наукових досліджень — чисельні методи та алгоритми факторізації.

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