THE FACTORIZATION OF THE 9TH FERMAT NUMBER

被引:31
作者
LENSTRA, AK
LENSTRA, HW
MANASSE, MS
POLLARD, JM
机构
[1] UNIV CALIF BERKELEY, DEPT MATH, BERKELEY, CA 94720 USA
[2] DEC SRC, PALO ALTO, CA 94301 USA
[3] TIDMARSH COTTAGE, READING RG8 8EX, BERKS, ENGLAND
关键词
FERMAT NUMBER; FACTORING ALGORITHM;
D O I
10.2307/2152957
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper we exhibit the full prime factorization of the ninth Fermat number F9 = 2(512) + 1. It is the product of three prime factors that have 7, 49, and 99 decimal digits. We found the two largest prime factors by means of the number field sieve, which is a factoring algorithm that depends on arithmetic in an algebraic number field. In the present case, the number field used was Q(fifth-root 2) . The calculations were done on approximately 700 workstations scattered around the world, and in one of the final stages a supercomputer was used. The entire factorization took four months.
引用
收藏
页码:319 / 349
页数:31
相关论文
共 49 条
[1]  
Andrews G. E., 1976, ENCY MATH ITS APPL, V2
[2]  
Brent R.P., 1986, AUSTRAL COMPUT SCI C, V8, P149
[3]  
BRENT RP, 1981, MATH COMPUT, V36, P627, DOI 10.1090/S0025-5718-1981-0606520-5
[4]  
Brillhart J., 1988, CONT MATH, V22
[5]  
BUCHMANN J, 1985, J NUMBER THEORY, V20, P192, DOI 10.1016/0022-314X(85)90040-X
[6]  
COHEN H, 1984, MATH COMPUT, V42, P297, DOI 10.1090/S0025-5718-1984-0726006-X
[7]  
COHEN H, 1987, MATH COMPUT, V48, P103, DOI 10.1090/S0025-5718-1987-0866102-2
[8]  
Conway J.H., 1976, NUMBERS GAMES
[9]  
Cunningham A, 1904, P LOND MATH SOC, V1, P175
[10]  
EULER Leonhard, 1732, COMM ACAD SCI PETROP, V6, P103