Factoring large numbers with a quadratic sieve
Mathematics of ComputationPublished 1 January 1983Open access
Joseph L. Gerver
Citations34
SJR quartileQ1
SJR score1.84
SNIP1.96
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The quadratic sieve algorithm was used to factor a 47-digit number into primes and a comparison with Wagstaff's results suggests that QS should be faster than CFEA when the number being factored exceeds 60 digits.
Abstract
The quadratic sieve algorithm was used to factor a 47-digit number into primes. A comparison with Wagstaff’s results using the continued fraction early abort algorithm suggests that QS should be faster than CFEA when the number being factored exceeds 60 digits (plus or minus ten or more digits, depending on details of the hardware and software).
Keywords
Computer Science
Journal of Number TheoryOn a problem of Oppenheim concerning “factorisatio numerorum”
328 Citations1983E. Rodney Canfield, Paul Erdős +1 more
SIAM Journal on ComputingOn the Asymptotic Complexity of Matrix Multiplication
206 Citations1982Don Coppersmith, S. Winograd
A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm.
Mathematics of ComputationA method of factoring and the factorization of 𝐹₇
170 Citations1975Michael A. Morrison, John Brillhart
Mathematics of ComputationAsymptotically fast factorization of integers
130 Citations1981John D. Dixon
It is proved that the expected number of operations which will be required is O(exp{ 83Qn n In In n)l/2) for some constant f > 0.
SIAM Journal on ComputingRapid Multiplication of Rectangular Matrices
86 Citations1982Don Coppersmith
The number of essential multiplications required to multiply matrices of size N and N is bounded by CN^2 \log ^2 N, where N is the number of matrices in a N-dimensional model.
Mathematics of ComputationAsymptotically Fast Factorization of Integers
29 Citations1981John D. Dixon