A practical analysis of the elliptic curve factoring algorithm

Authors:
Robert D. Silverman and Samuel S. Wagstaff

Journal:
Math. Comp. **61** (1993), 445-462

MSC:
Primary 11Y05; Secondary 11A51, 68Q25

DOI:
https://doi.org/10.1090/S0025-5718-1993-1122078-7

MathSciNet review:
1122078

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Much asymptotic analysis has been devoted to factoring algorithms. We present a practical analysis of the complexity of the elliptic curve algorithm, suggesting optimal parameter selection and run-time guidelines. The parameter selection is aided by a novel use of Bayesian statistical decision techniques as applied to random algorithms. We discuss how frequently the elliptic curve algorithm succeeds in practice and compare it with the quadratic sieve algorithm.

**[1]**Richard P. Brent,*Some integer factorization algorithms using elliptic curves*, Research Report CMA-R32-85, The Centre for Mathematical Analysis, The Australian National University, 1985.**[2]**J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr.,*Factorizations of**up to high powers*, 2nd ed., Contemp. Math., vol. 22, Amer. Math. Soc., Providence, RI, 1983. MR**715603 (84k:10005)****[3]**Tom R. Caron and Robert D. Silverman,*Parallel implementation of the quadratic sieve*, J. Supercomputing**1**(1988), 273-290.**[4]**N. G. DeBruijn,*On the number of uncancelled elements in the sieve of Eratosthenes*, Indag. Math.**12**(1950), 247-256.**[5]**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, 5th ed., Oxford Univ. Press, Oxford, 1979. MR**568909 (81i:10002)****[6]**Donald E. Knuth and Luis Trabb Pardo,*Analysis of a simple factorization algorithm*, Theor. Comp. Sci.**3**(1976), 321-348. MR**0498355 (58:16485)****[7]**H. W. Lenstra, Jr.,*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987). 649-673. MR**916721 (89g:11125)****[8]**Peter L. Montgomery,*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), 243-264. MR**866113 (88e:11130)****[9]**Carl Pomerance,*Analysis and comparison of some integer factoring algorithms*, Math. Centrum Tracts (H. W. Lenstra, Jr. and R. Tijdeman, eds.), 1984, pp. 89-140. MR**700260 (84i:10005)****[10]**Howard Raiffa and Robert Schlaifer,*Applied statistical decision theory*, MIT Press, Cambridge, MA, 1961. MR**0117844 (22:8618)****[11]**Robert D. Silverman,*The multiple polynomial quadratic sieve*, Math. Comp.**48**(1987), 329-340. MR**866119 (88c:11079)**

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y05,
11A51,
68Q25

Retrieve articles in all journals with MSC: 11Y05, 11A51, 68Q25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1122078-7

Keywords:
Elliptic curves,
Dickman's function,
smooth groups,
quadratic sieve,
factorization

Article copyright:
© Copyright 1993
American Mathematical Society