A PRACTICAL ANALYSIS OF THE ELLIPTIC CURVE FACTORING ALGORITHM

被引：2

作者：

SILVERMAN, RD ^{[1
]}

WAGSTAFF, SS ^{[1
]}

机构：

[1] PURDUE UNIV,DEPT COMP SCI,W LAFAYETTE,IN 47907

来源：

MATHEMATICS OF COMPUTATION | 1993年 / 61卷 / 203期

关键词：

ELLIPTIC CURVES; DICKMAN FUNCTION; SMOOTH GROUPS; QUADRATIC SIEVE; FACTORIZATION;

D O I：

10.2307/2152967

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：445 / 462

页数：18

共 11 条

[1] Brent R. P., 1985, CMAR3285 AUSTR NAT U
[2] Caron T. R., 1988, Journal of Supercomputing, V1, P273, DOI 10.1007/BF00154339
[3] de Bruijn NG., 1950, INDAGATIONES MATH, V12, P247
[4] Knuth D. E., 1976, Theoretical Computer Science, V3, P321, DOI 10.1016/0304-3975(76)90050-5
[5] FACTORING INTEGERS WITH ELLIPTIC-CURVES
LENSTRA, HW
[J]. ANNALS OF MATHEMATICS, 1987, 126 (03) : 649 - 673
[6] MONTGOMERY PL, 1987, MATH COMPUT, V48, P243, DOI 10.1090/S0025-5718-1987-0866113-7
[7] POMERANCE C, 1984, MATH CTR TRACTS, P89
[8] RAIFFA H, 1961, APPLIED STATISTICAL
[9] SILVERMAN RD, 1987, MATH COMPUT, V48, P329, DOI 10.1090/S0025-5718-1987-0866119-8
[10] Wright E., 1979, INTRO THEORY NUMBERS

← 1 2 →