A Practical Analysis of the Elliptic Curve Factoring Algorithm

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 techn...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 1993-07, Vol.61 (203), p.445-462
Main Authors: Silverman, Robert D., Wagstaff, Samuel S.
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Curves
Decimals
Digital rights management
Exact sciences and technology
Expected values
Factorization
Integers
Mathematics
Number theory
Prime numbers
Run time
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5718
1088-6842
DOI:10.1090/S0025-5718-1993-1122078-7