A practical analysis of the elliptic curve factoring algorithm

Silverman, Robert D.; Wagstaff, Samuel S.

doi:10.1090/S0025-5718-1993-1122078-7

A practical analysis of the elliptic curve factoring algorithm
HTML articles powered by AMS MathViewer

by Robert D. Silverman and Samuel S. Wagstaff PDF

Math. Comp. 61 (1993), 445-462 Request permission

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.

References

Some integer factorization algorithms using elliptic curves

John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603

Parallel implementation of the quadratic sieve

1

On the number of uncancelled elements in the sieve of Eratosthenes

12

G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
Donald E. Knuth and Luis Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci. 3 (1976/77), no. 3, 321–348. MR 498355, DOI 10.1016/0304-3975(76)90050-5
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
Howard Raiffa and Robert Schlaifer, Applied statistical decision theory, Studies in Managerial Economics, Harvard University, Graduate School of Business Administration, Division of Research, Boston, Mass., 1961. MR 0117844
Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8