ПРОСІЮВАННЯ ПРОБНИХ ЗНАЧЕНЬ В МЕТОДІ МНОЖИННОГО КВАДРАТИЧНОГО k-РЕШЕТА НА ОСНОВІ СИГНАЛЬНИХ ОСТАЧ (Ukrainian)

Sieving of test values in multiple qudatatice k-sieve method based on signal remainings. (English)
Просеивание пробных значений в методе множественного квадратичного k-решета на основе сигнальных остатков (Russian)

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 Bsmooth 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 Y (X ) , the values are close to log(Y(X )) and Σ^pfaj=1sj log pj, 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 Y(X)mod(psj)=0, 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) = X² – 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 10¹⁸) to 1,541 (for N numbers size of 10³²) times with its monotone growth with increasing N. [ABSTRACT FROM AUTHOR]

Предложено способ прореживания пробных значений Х для метода множенственного квадратичного k-решета (MQkS), который является модификацией квадратичного решета (QS), в котороем выполняеэтся предварительное просеивание Х но основе сравнения сигнальних остатков Y*(X) с остатками Y(X) = X² - kN, где сигнальные остатки -это произведение первых степеней множителей Y(X). Установлено, что время расчета достаточного количества В-гладких зависит от значения параметра h в условии Y*(X) > h ·Y(X) где лучние значения времени были получены при h ≥ 0,7, которые почти в двое меньше чем время которое было получено при h = 0. При этом, с ростом N целесообразно увеличивать значение h. Показано, что дальнейшее снижение вычислительной сложности можно достич за счёт поиска только тех В-гладких, для которых показатели степени делителей В-гладкого могут превышать еденицу только при отностительно малых значениях элементов факторной базы, макимальная величина которых определяется на основе значений параметра kff. Установлено, что в сравнении з результатами экспериментов для значения параметра kff = 1 (ограничения отсутствуют) время расчёта уменьшалось на величину от 1.128 (для чисел N порядка 10¹⁸) до 1,541 (для чисел N порядка 10³²) раз при его монотонном росте с ростом N. [ABSTRACT FROM AUTHOR]

Copyright of Ukrainian Scientific Journal of Information Security is the property of National Aviation University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)