FACTORING WITH 2 LARGE PRIMES

被引:12
作者
LENSTRA, AK [1 ]
MANASSE, MS [1 ]
机构
[1] DIGITAL EQUIPMENT CORP, SYST RES CTR, PALO ALTO, CA 94301 USA
关键词
FACTORING ALGORITHM;
D O I
10.2307/2153299
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We describe a modification to the well-known large prime variant of the multiple polynomial quadratic sieve factoring algorithm. In practice this leads to a speed-up factor of 2 to 2.5. We discuss several implementation-related aspects, and we include some examples. Our new variation is also of practical importance for the number field sieve factoring algorithm.
引用
收藏
页码:785 / 798
页数:14
相关论文
共 19 条
[1]  
Bernstein D.J., 1993, LECT NOTES MATH, V1554, P103, DOI DOI 10.1007/BFB0091541
[2]  
Brillhart J., 1988, CONT MATH, V22
[3]   A POLYNOMIAL-TIME ALGORITHM TO FIND THE SHORTEST CYCLE BASIS OF A GRAPH [J].
HORTON, JD .
SIAM JOURNAL ON COMPUTING, 1987, 16 (02) :358-366
[4]  
LAMACCHIA BA, 1991, LECT NOTES COMPUT SC, V537, P109
[5]  
LENSTRA AK, 1992, LECT NOTES COMPUT SC, V583, P344
[6]  
LENSTRA AK, 1991, LECT NOTES COMPUT SC, V473, P72
[7]   THE FACTORIZATION OF THE 9TH FERMAT NUMBER [J].
LENSTRA, AK ;
LENSTRA, HW ;
MANASSE, MS ;
POLLARD, JM .
MATHEMATICS OF COMPUTATION, 1993, 61 (203) :319-349
[8]  
LENSTRA AK, 1990, LECT NOTES COMPUT SC, V434, P355
[9]  
LENSTRA AK, 1993, LECT NOTES MATH, V1554, P11
[10]  
LENSTRA AK, 1993, LECTURE NOTES MATH, V1554