China
Africa
Explore chapters and articles related to this topic
*Algorithms for Factoring and Computing Discrete Logarithms
Published in Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography, 2020
The fastest known general-purpose factoring algorithm is the general number field sieve. Heuristically, this algorithm factors its input N in expected time 2O((logN)1/3⋅(loglogN)2/3), which is sub-exponential in the length of N.
Integer Factorization Problem
Published in Khaleel Ahmad, M. N. Doja, Nur Izura Udzir, Manu Pratap Singh, Emerging Security Algorithms and Techniques, 2019
Pinkimani Goswami, Madan Mohan Singh
The NFS method is considered as the fastest method for factoring a large number. Like the other factoring method, this method has also used the congruence x2≡y2modn to find the factors of n, but this time computation is done in a ring of algebraic integers. The NFS method was first designed for some integer of a special form, and this variant is called special number field sieve (SNF) method (Lenstra et al., 1993). Later in 1992, this algorithm is modified for arbitrary integer and named as general number field sieve (GNFS) or NFS method.
Number-Theoretic Reference Problems
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
The number field sieve was first proposed by Pollard [987] and refined by others. Lenstra et al. [752] described the special number field sieve (SNFS) for factoring integers of the form re − s for small positive r and |s|. A readable introduction to the algorithm is provided by Pomerance [995]. A detailed report of an SNFS implementation is given by Lenstra et al. [751]. This implementation was used to factor the ninth Fermat number F9 = 2512 + 1, which is the product of three prime factors having 7, 49, and 99 decimal digits. The general number field sieve (GNFS) was introduced by Buhler, Lenstra, and Pomerance [219]. Coppersmith [269] proposed modifications to the GNFS which improve its running time to Ln[13,1.902], however, the method is not practical; another modification (also impractical) allows a precomputation taking Ln[13,2.007] time and Ln[13,1.639] storage, following which all integers in a large range of values can be factored in Ln[13,1.639] time. A detailed report of a GNFS implementation on a massively parallel computer with 16384 processors is given by Bernstein and Lenstra [122]. See also Buchmann, Loho, and Za-yer [217], and Golliver, Lenstra, and McCurley [493]. More recently, Dodson and Lenstra [356] reported on their GNFS implementation which was successful in factoring a 119-decimal digit number using about 250 mips years of computing power. They estimated that this factorization completed about 2.5 times faster than it would with the quadratic sieve. Most recently, Lenstra [746] announced the factorization of the 130-decimal digit RSA-130 challenge number using the GNFS. This number is the product of two 65-decimal digit primes. The factorization was estimated to have taken about 500 mips years of computing power (compare with Table 3.3). The book edited by Lenstra and Lenstra [749] contains several other articles related to the number field sieve.
A Framework for Filtering Step of Number Field Sieve and Function Field Sieve
Published in IETE Journal of Research, 2023
Rahul Janga, R. Padmavathy, S. K. Pal, S. Ravichandra
In 1988, Pollard gave a new approach for factoring integers. Hendrik Lenstra developed this method into the Special Number Field Sieve (SNFS). Later through a collaboration of several researchers, the General Number Field Sieve (GNFS) was developed. Initially, there was wide skepticism as to whether this method would be practical, but those doubts have been dispelled [9].