Acceleration of the quadratic sieve method based on the additional search of B-smooth numbers
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2018.1.08Keywords:
factorization, quadratic sieve method, B-smooth, conditionally B-smoothAbstract
We will investigate the degree of acceleration of the basic quadratic sieve method based on the search for conditionally B-smooth numbers. An analysis is made of the influence, and the number of cases of using conditionally B-smooth numbers. It is shown that the modified algorithm based on the search for conditionally B-smooth numbers allows to factor the number in those cases when the basic quadratic sieve algorithm (with the standard sieving interval and the size of the factor base) could not form a matrix for obtaining the solution.References
Pomerance C. The quadratic sieve factoring algorithm / C. Pomerance // Advances in Cryptology (T. Beth, N. Cot and I. Ingemarrson eds.), Lecture Notes in Comput. Sei. — Paris, 1985. — P. 169–182.
Lindquist E. The Quadratic Sieve Factoring Algorithm / E. Lindquist // Math 488: Cryptographic Algorithms, Diciembre. — New York, 2001. — P. 1–11.
Pomerance C. Analysis and comparison of some integer factoring algorithms / C. Pomerance // Mathematisch Centrum Computational Methods in Number Theory, Pt. 1. — Amsterdam: Math Centre Tract 154, 1982. — P. 89–139.
Pomerance C. Smooth numbers and the quadratic sieve / C. Pomerance // Proc. of an MSRI workshop. — New York: Proc. Amer. Math. Soc. 115, 2008. — P. 69–81.
Song Y. Quadratic Sieve / Y. Song // Primality Testing and Integer Factorization in Public-Key Cryptography Second Edition. — New York: Springer, 2008. — P. 234–239.
Crandall R. Smooth numbers and the quadratic sieve / R. Crandall, C. Pomerance // Prime Numbers A Computational Perspective Second Edition. — New York: Springer, 2005. — P. 261–315.
Gorbenko I.D. Analiz kanalov ujazvimosti sistemy RSA / I.D. Gorbenko, V.I. Dolgov, A.V. Potij, V.N. Fedorchenko // Bezopasnost' informatsii. — 1995. — № 2. — S.22–26.
Brown D. Breaking RSA May Be As Difficult As Factoring [Digital source] / Daniel R.L. Brown // Cryptology ePrint Archive. — 2005. — Available at: https://eprint.iacr.org/2005/380.
