# METHOD OF MULTIPLE POLINOMIAL k-SIEVE WITH USING OF SIGNAL REMINDERS DURING SIEVING OF PROBABLE VALUES

S.D. Vynnychuk, V.M. Misko

Èlektron. model. 2018, 41(2):03-22
https://doi.org/10.15407/emodel.41.02.003

### ABSTRACT

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)) < 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.

### KEYWORDS

integer factoring, quadratic sieve, multiple sieve.

### REFERENCES

1. Gorbenko, I.D., Dolgov, V.I., Potiy, A.V. and Fedorchenko, V.N. (1995), “Channel analysis of the RSA system vulnerability”, Bezopansost informasii, no. 2, pp. 22-26.
2. Brown Daniel, R.L. “Breaking RSA May Be As Difficult As Factoring”, available at: http://www.pgpru.com/novosti /2005/1026vzlomrsabezfaktorizaciirealennoneeffektiven.
3. Kannan, B. and Rajakani, M. (2018), “Algorithmic strategies for solving complex problems in cryptography. Advances in information security, privacy, and ethics (AISPE) book series”, IGI Global, Hershey, Pennsylvania, USA.