S.D. Vynnychuk, V.M. Misko
Èlektron. model. 2018, 41(2):03-22
An algorithm for the method of a Multiple Quadratic k-Sieve (MQkS) is proposed, which is aAn algorithm for the method of a Multiple Quadratic k-Sieve (MQkS) is proposed, which is amodification of the quadratic sieve method (QS), in which, when sieving test values, it is proposedto perform a preliminary sieving on the basis of the comparison, the remainder yk(X) = X2 - kN (k ≥ 1) with signaling residuesy yk*(X), where yk*(X) is the product of the first powersof the factors yk(X). Among the test values, the ones for which log (yk*(X)) < h log (yk*(X)), where a real number h ∈ [0,1] is a parameter that can be selected. It is established that at growth N the value of h increases, at which the lowest value of the calculation time is reached. It is also establishedthat a decrease in the time of obtaining a sufficient number of B-smooth ones can be obtainedby limiting the parameters of powers of the B-smooth divisors exceeding the unit for a pluralityof elements of a common factor base, greater than a certain value, which is determined onthe basis of the value of the parameter kff. On the basis of numerical experiments with relativelysmall numbers of order 10m at m = 20÷32, it is shown that the time of calculating a sufficient numberof B-smooth is a function of the introduced parameter kff, with a monotonically increasing ratioof calculation timewith the value of the parameter kff = 1 (no restriction) to theminimumtime. Thesteps of the algorithm of the method and the ideas of their implementation are described. A heuristicestimation of the complexity of the MQkS method for a number of values of the parameter pla is given.
integer factoring, quadratic sieve, multiple sieve.