Factoring with Two Large Primes

We describe a modification to the well-known large prime variant of the multiple polynomial quadratic sieve factoring algorithm. In practice this leads to a speed-up factor of 2 to 2.5. We discuss several implementation-related aspects, and we include some examples. Our new variation is also of prac...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 1994, Vol.63 (208), p.785-798
Main Authors: Lenstra, A. K., Manasse, M. S.
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Computer memory
Exact sciences and technology
Factorization
Gaussian elimination
Integers
Mathematics
Number theory
Numbers
Polynomials
Prime numbers
Sciences and techniques of general use
Vertices
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a modification to the well-known large prime variant of the multiple polynomial quadratic sieve factoring algorithm. In practice this leads to a speed-up factor of 2 to 2.5. We discuss several implementation-related aspects, and we include some examples. Our new variation is also of practical importance for the number field sieve factoring algorithm.
ISSN:0025-5718
1088-6842
DOI:10.1090/S0025-5718-1994-1250773-9