The way of effective use of incremental with multiple thinning of test values for Fermat's factoring method
DOI:
https://doi.org/10.20535/2411-1031.2016.4.1.96080Keywords:
RSA algorithm, factorization, Fermat's algorithm, the sieve method, thinning of test values.Abstract
Among the modern methods of cryptographic information protection asymmetric algorithms is most widely used. A special place among them is occupied by RSA (Rivest-Shamir-Adleman) encryption algorithm, which recommended the use a number of international standards and recommendations. RSA cryptographic resistance is based on the difficulty of the task execution of multi-digit numbers factorization and is not an effective problem of compromising its software and hardware implementations. Currently the “fastest” ways of decomposition the big numbers into factors are methods of the general number field sieve (GNFS), the quadratic sieve (QS) algorithm and the elliptic curve factorization method (ECM). It is known that the basis of these methods are based on a number of fundamental relations of Fermat’s classical algorithm, proceeding from which it can be argued that the improvement of Fermat’s method can have an impact on reducing the computational complexity of modern factorization methods listed above. One of the ways to increase the efficiency of the improved Fermat's factoring method is a modification of existing or developing new algorithms of execution the algebraic operations with large numbers. Among these can be the operation of the modular division in procedures for advance sieving of test values X. A modified method of thinning test values in Fermat’s factoring algorithm is proposed, the main advantage of which is the refusal to perform complex arithmetic operations of modular division of large sequences and replacing them with the procedure of the modular division of small numbers.
References
D. Brown, “Breaking RSA May Be As Difficult As Factoring”, Journal of Cryptology, vol. 29, iss. 1, pp. 220-241, January 2016. doi: 10.1007/s00145-014-9192-y.
O.N. Vasilenko. Number-theoretic algorithms in cryptography. Moskow, Russia: MTsNMO, 2003.
Sh.T. Ishmukhametov. Factoring methods of integers. Kazan, Republic of Tatarstan: Kazan Federal University, 2011.
A.V. Korneiko, and A.V. ZHilin, “Analysis of the known methods for computing the factorization of large numbers”, Modelling Problems in Power Engineering, iss. 61, pp. 3-13, 2011.
D. Knut. Art of Computer Programming. Vol. 2. Москва, Moskow, Russia: Мir, 1979.
“RSA. Security Solutions to Address Cyber Threats”. [Online]. Available: https://www.rsa.com. Accessed on: Jan. 19, 2016.
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).
