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

Степан Дмитрович Винничук, Віталій Миколайович Місько

Анотація


Запропоновано спосіб проріджування пробних значень Х для методу множинного квадратичного k-решета (MQkS), що є модифікацією методу квадратичного решета (QS), в якій здійснюється попереднє просіювання Х на основі порівнянь сигнальних остач Y*(X) з остачами Y(X) = X2 – kN, де сигнальні остачі – це добуток перших степенів множників Y(X). Встановлено, що час обчислення достатньої кількості В-гладких залежить від значення параметра h в умові Y*(X) > h ×Y(X) де кращі значення часу отримуються при h ³ 0,7, які майже вдвічі менші за час, що відповідає h = 0. При цьому з ростом N доцільно збільшувати значення h. Показано, що подальше зниження обчислювальної складності можна досягнути за рахунок пошуку тільки тих В-гладких, для яких показники степенів дільників В-гладкого можуть перевищувати одиницю лише при відносно малих значеннях елементів факторної бази, максимальна величина яких визначається на основі значення параметра kff. Встановлено, що в порівнянні з даними розрахунків для значення параметра kff = 1 (обмеження відсутні) час розрахунку зменшувався на величину від 1,128 (для чисел N порядку 1018) до 1,541 (для чисел N порядку 1032) разів при його монотонному рості з ростом N.

 


Ключові слова


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

Посилання


И. Горбенко, В. Долгов, А. Потий, В. Фе-дорченко, "Анализ каналов уязвимости системы RSA", Безопасность информации, № 2, С. 22-26, 1995.

D. Brown, Breaking RSA May Be As Difficult As Factoring. [Electronic resource]. Online: http://www. pgpru.com/novosti/2005/1026vzlomrsabezfaktorizaciirealennoneeffektiven.

K. Balasubramanian; M. Rajakani, "Algorith-mic strategies for solving complex problems in cryptography", Advances in information security, privacy, and ethics (AISPE) book series. Hershey, Pennsylvania, IGI Global, 2018.

Quadratic sieve. [Electronic resource]. Online: https://en.wikipedia.org/wiki/Quadratic_sieve.

RSA numbers. [Electronic resource]. Online: https://en.wikipedia.org/wiki/RSA_numbers.

C. Pomerance, "Smooth numbers and the quadratic sieve. Algorithmic Number Theory: Lattices, Number Fields", Curves and Cryptography, MSRI Publications, pp. 69–81, 2008

A. Vazzana, D. Garth, M. Erickson, Introduc-tion to number theory. Boca Raton: Chapman & Hall/CRC, 2015.

V. Zhenyu Guo; W. Banks, Exponential sums, character sums, sieve methods and distribution of prime numbers, 2017.

R. Crandall, C. Pomerance, Prime numbers a computational perspective (Second ed.), New York, NY: Springer, 2010.

Ш. Ишмухаметов, Методы факторизации натуральных чисел, Казан. ун. Казань, 2011, 190 с.

С. Винничук, В. Місько, "Метод множин-ного k-решета цілочисельної факторизації", Елек-тронне моделювання, Т. 40, № 5, С. 3-22, 2018.

S. Padhye; A. Rajeev, Introduction to Crypto-graphy. Boca Raton, FL : CRC Press, 2018.

E. Landquist, "The Quadratic Sieve Factoring Algorithm", MATH 488: Cryptographic Algorithms, 2001

О. Василенко, Теоретико–числовые алго-ритмы в криптографии, 2003, 328 с.


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

Посилання

  • Поки немає зовнішніх посилань.


ISSN  2411-071X (Online), ISSN 2225-5036 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory