Sieving of test values in multiple qudatatice k-sieve method based on signal remainings

Abstract

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 p_j - are prime numbers (elements of the quotient base). At the same time, since the possible values s_j > 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) = 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.