Factoring with two large primes
[For the entire collection see Zbl 0755.00009.] Integer factoring algorithms are of great importance in cryptology. The paper presents a new technique that proved to be extremely useful, not only to speed-up well-known factoring algorithms, but also to introduce a new factoring algorithm. Until 1989 the best practical general purpose factoring algorithm was the quadratic sieve algorithm (mpqs, for short) with heuristic expected run time \(\exp((1+o(1))(\log n)^{1/2}(\log\log n)^{1/2})\). By this algorithm a record factorization of a 106 digit integer in 1989 was done. The mpqs works in two stages. In the first stage relations of the form \(\nu^ 2\equiv\prod p^{e_{\nu p}}\bmod n\) are collected, where \(e_{\nu p}\) is an integer \(\geq 0\) and the product ranges over the number \(-1\) and the primes less some bound \(B\). In the second stage one uses these relations to find integer solutions to \(x^ 2\equiv y^ 2\bmod n\). Each such solution has a good chance to lead to a factorization of \(n\) by computing \(\text{gcd}(n,x\pm y)\). A new factoring algorithm, the so-called number field sieve (nfs) presented by the authors together with H. W. Lenstra and J. M. Pollard, was introduced as a special purpose algorithm which applies to \(n\) of the form \(r^ e-s\), where \(r\) is a small positive integer, and \(s\) is a non- zero integer of small absolute value. The heuristic expected run time of nfs is \(\exp((c+ o(1))(\log n)^{1/3}(\log\log n)^{2/3})\) with \(c=2(2/3)^{2/3}\). It is suspected that a generalization of nfs to integers of arbitrary form will run in time of the basic algorithm, though with a slightly bigger value for \(c\). The authors explain how to use two large primes with nfs. The practical consequences remain to be studied.
- Comparison of the efficiency of the factoring algorithms of Morrison-Brillhart and Schroeppel
- Modifications to the number field sieve
- Rigorous analysis of a randomised number field sieve
- Parameter trade-offs for NFS and ECM
- Fast generation of prime numbers and secure public-key cryptographic parameters.
- Integer factorization as subset-sum problem
- Using Lucas sequences to factor large integers near group orders.
- Factoring N=p^rq^s for Large r and s
- Factoring integers by CVP algorithms
- Square Root Algorithms for the Number Field Sieve
- Short Notes: Factoring Medium-Sized Integers
- Running Time Predictions for Factoring Algorithms
- A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
- Asymptotically Fast Factorization of Integers
- A Rigorous Time Bound for Factoring Integers
- scientific article; zbMATH DE number 475432 (Why is no real title available?)
- Factoring with Two Large Primes
- scientific article; zbMATH DE number 708815 (Why is no real title available?)
- scientific article; zbMATH DE number 733561 (Why is no real title available?)
- On the factorization of RSA-120
- The magic words are squeamish ossifrage. (Extended abstract)
- Factoring Integers with Large-Prime Variations of the Quadratic Sieve
- Integer factoring using small algebraic dependencies
- MPQS with three large primes
- Practical improvements to class group and regulator computation of real quadratic fields
- Factoring N=p^rq for large r
- Generation of Elements with Small Modular Squares and Provably Fast Integer Factoring Algorithms
- On finding Fermat’s pairs
- Differential Factoring for Integers
- One approach to factorization of positive integers
This page was built for publication: Factoring with two large primes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036860)
