1987/01/01 by Robert Silverman · 2 citations
Computer Science · Mathematics · #Polynomial and algebraic computation #Coding theory and cryptography #Cryptography and Residue Arithmetic #Mathematics #Quadratic equation #Factorization #Sieve (category theory) #Polynomial #Factoring #Range (aeronautics) #Factorization of polynomials #Discrete mathematics #Combinatorics #Algorithm #Matrix polynomial #Mathematical analysis
paper · doi:10.1090/s0025-5718-1987-0866119-8
openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
A modification, due to Peter Montgomery, of Pomerance’s Quadratic Sieve for factoring large integers is discussed along with its implementation. Using it, allows factorization with over an order of magnitude less sieving than the basic algorithm. It enables one to factor numbers in the 60-digit range in about a day, using a large minicomputer. The algorithm has features which make it well adapted to parallel implementation.