Sieving of test values in multiple qudatatice k-sieve method based on signal remainings
Наукові журнали НАУ
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Sieving of test values in multiple qudatatice k-sieve method based on signal remainings
Просеивание пробных значений в методе множественного квадратичного k-решета на основе си-гнальных остатков Просіювання пробних значень в методі множинного квадратичного k-решета на основі сигнальних остач |
|
| Creator |
Винничук, Степан Дмитрович; Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Місько, Віталій Миколайович; Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
|
| Subject |
Information security
integer factoring; quadratic sieve; multiple sieve UDC 511:003.26.09 Информационная безопасность целочисленная факторизация; метод квадратичного решета; множественное решето УДК 511:003.26.09 Інформаційна безпека цілочисельна факторизація; метод квадратичного решета; множинне решето УДК 511:003.26.09 |
|
| Description |
A method for the thining of the test values of X for the method of the multiple quadratic k-sieve (MQkS), which is a modification of the quadratic sieve (QS) method. Important characteristics of the QS method and its modifications are the size of the factor base and the screening interval that significantly affect the rate of obtaining B-smooth numbers. The search for these figures is carried out using a screening procedure in which the searches for those of the trial X are, for the remainder , the values are close to and , where pj - are prime numbers (elements of the quotient base). At the same time, since the possible values sj > 1, it is necessary to determine the value of X, under which , in the case of frequent polynomial changes, it leads to appreciable growth of computational costs. This article is devoted to the development of a method for screening test X for a modified algorithm of the MQkS method, which is characterized by a frequent change of the polynomial. Tpreliminary thining of X is carried out on the basis of comparisons of the signal remains Y*(X) with the remainders Y(X) = X2 – kN, where the signal remains is a product of the first powers of the factors Y(X). An estimate of the quantity B-smooth for which the condition Y*(X) > h ×Y(X) is satisfied. It is established that the time of computing a sufficient number of B-smooth depends on the value of the parameter h in the condition Y*(X) > h ×Y(X) where the best time values are obtained at h ³ 0,7, which is almost twice less than the time corresponding to h = 0. At the same time, with the growth of N it is expedient to increase the value of h.. It is shown that further reduction of computational complexity can be attained by the search of only those B-smooth, for which the indicators of the degree of divisors of B-smooth can exceed the element only with relatively small values of elements of the factor base, whose maximal value is determined on the basis of the values of the parameter kff. It has been established that in comparison with the experimental results for the value of the parameter kff = 1 (no restrictions), the calculation time was reduced by a value from 1,128 (for numbers N size of 1018) to 1,541 (for N numbers size of 1032) times with its monotone growth with increasing N.
Предложено способ прореживания пробных значений Х для метода множенственного квадратичного 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. Запропоновано спосіб проріджування пробних значень Х для методу множинного квадратичного 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. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2019-04-25
|
|
| Type |
—
— — |
|
| Format |
application/pdf
application/pdf application/pdf |
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/Infosecurity/article/view/13446
10.18372/2225-5036.25.13446 |
|
| Source |
Безпека інформації; Том 25, № 1 (2019); 45-52
Безопасность информации; Том 25, № 1 (2019); 45-52 Ukrainian Scientific Journal of Information Security; Том 25, № 1 (2019); 45-52 |
|
| Language |
uk
|
|