Improvement of the quadratic sieve method on the basis of the extended factor base and using available quantity of B – smooth numbers
DOI:
https://doi.org/10.20535/2411-1031.2017.5.2.136966Keywords:
Quadratic sieve, extended factor base, available quantity of B-smooth, sieving interval, prime numbers.Abstract
In information and telecommunication systems, RSA algorithms are often used to solve information security problems. At the core of the cryptostability of the most popular today asymmetric cryptographic algorithm RSA is the complexity of the factorization of large integers. Quadratic sieve method is the best for factorization of integers under 110 decimal digits or so. The most time consuming part of the algorithm of a quadratic sieve is the sieving process. The size of the factor base is one of the key parameters that determine the effectiveness of the sieving algorithm. Too large factor base requires the search for a large number of B–smooth numbers, which increases the total execution time of the algorithm. When the size is less than necessary, it will not be possible to find a sufficient number of B–smooth numbers. In this paper, the method for determining and applying a sufficient size of B–smooth numbers with doubling the factor base size in comparison with the basic algorithm of a quadratic sieve is proposed. With the expansion of the factor base, the number of N numbers increases, which can be decomposed into factors by the quadratic sieve method. It is also noted that its increase leads to an increase in computational complexity, since it is advisable to find a greater number of B–smooth numbers. However, when conducting numerical experiments, where the size of the factor base increased twice, it turned out that using the proposed algorithm, the time necessary to find a sufficient number of B-smooth numbers, on the contrary, decreased.
References
C. Pomerance, “The quadratic sieve factoring algorithm”, in Proc. of EUROCRYPT 84. A Workshop on the Theory and Application of Cryptographic Techniques, Paris, 1984. pp. 169-182.
doi: 10.1007/3-540-39757-4_17.
Landquist E. “The Quadratic Sieve Factoring Algorithm”. [Online]. Available: http://www.cs.virginia.edu/crab/QFS_Simple.pdf . Accessed on: Sept. 19, 2017.
C. Pomerance “Analysis and comparison of some integer factoring algorithms”, in Computational Methods in Number Theory, vol. 154, Amsterdam, Netherlands: Math. Centre Amsterdam, 1982, pp. 89-139.
C. Pomerance, “Smooth numbers and the quadratic sieve”, Algorithmic Number Theory, vol. 44, pp. 69-81, 2008.
Y.Y.Song, Primality testing and integer factorization in public-key cryptography, New York, USA: Springer Publishing, 2009.
doi: 10.1007/978-0-387-77268-4.
R. Crandall, and C. Pomerance, Prime Numbers. A Computational Perspective, New York, USA: Springer Publishing, 2005.
I.D Gorbenko, V.I. Dolgov, A.V. Potiy, and V.N. Fedochenko, “Analysis of RSA system vulnerability channels”, Information security, no. 2, pp. 22-26, 1995.
Daniel R. L. Brown, “Breaking RSA may be as difficult as factoring”. [Online]. Available: https://eprint.iacr.org/2005/380.pdf. Accessed on: Sept. 19, 2017.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Collection "Information technology and security"
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors that are published in this collection, agree to the following terms:
- The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
- The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
- Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).
