2. Home
  3. ARCHIVE
  4. 2019
  5. VOL 41, NO 2 (2019)
  6. pp. 03-22

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

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.
4. “Quadratic sieve”, available at: https://en.wikipedia.org/wiki/Quadratic_sieve.
5. Silverman, R.D (1987), “The multiple polynomial quadratic sieve”, Math. Comp, Vol. 48 (177), pp. 329-339.
https://doi.org/10.1090/S0025-5718-1987-0866119-8
6. Vynnychuk, S.D. and Misko, V.M. (2018), “Method of multiple quadratic k-sieve integer factorization”, Elektron. modelirovanie, Vol. 40, no. 5, pp. 3-26, available at: 
https://doi.org/10.15407/emodel.40.05.003
7. Vasilenko, O.N. (2003), Teoretiko-chislovyie algoritmy v kriptografii [Number-Theoretic Algorithms in Cryptography], MTsNMO, Moscow, Russia.
8. Ishmukhametov, Sh.T. (2011), Metody faktorizatsii naturalnykh chisel [Methods of natural numbers factorization], Kasanskiy Universitet, Kasan, Russia.
9. Landquist, E. (2001), “The Quadratic Sieve Factoring Algorithm”, MATH: Cryptographic Algorithms, no. 488, pp. 1-11.
10. Vynnychuck, S. and Misko, V. (2018), “Acceleration analysis of the quadratic sieve method based on the online matrix solving”, Eastern-European Journal of Eenterprise Technologies / Mathematics and cybernetics, Vol. 2, no. 4 (92), pp. 33-38, 
https://doi.org/10.15587/1729-4061.2018.127596

Full text: PDF