2. Home
  3. ARCHIVE
  4. 2018
  5. VOL 40, NO 5 (2018)
  6. pp. 03-26

THE METHOD OF MULTIPLE QUADRATIC K-SILVE INTEGER FACTORIZATION

S.D. Vynnychuk, V.M. Misko
THE GEORGY PUKHOV INSTITUTE FOR ENERGY MODELLING THE NATIONAL ACADEMY OF SCIENCES OF UKRAINE

Èlektron. model. 2018, 40(5):03-26
https://doi.org/10.15407/emodel.40.05.003

ABSTRACT

A modification of the quadratic sieve method (QS) was proposed, in which the search for B-smooth numbers uses the polynomials X2- kN. In contrast to the QS and multiple polynomial quadratic sieve (MPQS) methods, the method ùà multiple quadratic k-sieve (MQkS) uses a common factor base (FB), which was detailed for each k value. The algorithm takes into account the fact that, the number of B-smooth is relatively larger with smaller values of the numbers of the sifting interval. It was confirmed by the data of numerical experiments. The steps for the proposed algorithm and their implementation were described. On the basis of numerical experiments, it was demonstrated that, using of the MQkS method, it is possible to achieve a decrease in the average time of the formation of the B-smooth set over against of the QS method with a smaller size of FB.

KEYWORDS

integer factoring, quadratic k-sieve, multiple sieve.

REFERENCES

  1. Gorbenko, D., Dolgov, V.I., Potiy, A.V., Fedorchenko, V.N. (1995). Analiz kanalov uyazvimosti sistemyi RSA. Bezopasnost’ informatsii, 2, 22–26.
  2. Daniel L. Brown. Breaking RSA May Be As Difficult As Factoring. Retrieved from: http://www.pgpru.com/novosti/2005/1026vzlomrsabezfaktorizaciirealennoneeffektiven.
  3. Kannan Balasubramanian; M Algorithmic strategies for solving complex problems in cryptography. // Advances in information security, privacy, and ethics (AISPE) book series. Hershey, Pennsylvania (701 E. Chocolate Avenue, Hershey, Pennsylvania, 17033, USA) : IGI Global, [2018].
  4. Quadratic Retrieved from: https://en.wikipedia.org/wiki/Quadratic_sieve.
  5. The Quadratic Sieve Factoring Algorithm Eric Landquist MATH 488: Cryptographic Algorithms December 14, 2001.
  6. RSA Retrieved from: https://en.wikipedia.org/wiki/RSA_numbers.
  7. Carl Smooth numbers and the quadratic sieve. Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, MSRI Publications, 44:69-81, 2008.
  8. Anthony Vazzana; David Garth; Martin J Introduction to number theory. Boca Raton : Chapman & Hall/CRC, 2015.
  9. Victor Zhenyu Guo; William David Exponential sums, character sums, sieve methods and distribution of prime numbers. [Columbia, Missouri] : [University of Missouri], May, 2017.
  10. Crandall, , & Pomerance, C.B. (2010). Prime numbers a computational perspective (Seconded.). New York, NY: Springer.
  11. Ishmuhametov,T. (2011). Metodyi faktorizatsii naturalnyih chisel. Kasan: Kasan Un.
  12. Sahadeo Padhye; Rajeev Anand Sahu; Vishal Introduction to Cryptography. Boca Raton, FL : CRC Press, 2018. https://doi.org/10.1201/9781315114590
  13. Misko, (2018). Pryskorennia metodu kvadratychnoho resheta na osnovi vykorystanni umovno B-hladkykh  hysel. Zbirnyk « System research and information technologies», 1.
  14. Vinnichuk, & Misko, V. (2017). Pryskorennia metodu kvadratychnoho resheta na osnovi vykorystanni rozshyrenoi faktornoi bazy ta formuvannia dostatnoi kilkosti B-hladkykh chysel. Zbirnyk «Information technology and security», 5, 2nd ser.
  15. Vynnychuck , Misko V. Acceleration analysis of the quadratic sieve method based on the online matrix solving. // Mathematics and cybernetics – applied aspects., 2018. DOI: 10.15587/1729-061.2018.133603
  16. Silverman D. The multiple polynomial quadratic sieve // Math. Comp. 1987. V. 48 (177). P. 329-339. https://doi.org/10.1090/S0025-5718-1987-0866119-8
  17. D. Breitenbacher, I. Homoliak, J. Jaros, P. Hanacek. Impact of Optimization and Parallelism on Factorization Speed of SIQS. Journal of Systemics 2016; 4 (3), 51-58.

Full text: PDF