|
Three new factors of Fermat numbers
Author(s):
R.
P.
Brent;
R.
E.
Crandall;
K.
Dilcher;
C.
Van Halewyn.
Journal:
Math. Comp.
69
(2000),
1297-1304.
MSC (1991):
Primary 11Y05, 11B83, 11Y55;
Secondary 11-04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25
Posted:
March 1, 2000
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We report the discovery of a new factor for each of the Fermat numbers  . These new factors have 27, 33 and 27 decimal digits respectively. Each factor was found by the elliptic curve method. After division by the new factors and previously known factors, the remaining cofactors are seen to be composite numbers with  ,  and  decimal digits respectively.
References:
-
- 1.
- R. P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149-163.
Also Report CMA-R32-85, Centre for Mathematical Analysis, Australian National University, Canberra, Sept. 1985, 20 pp. - 2.
- R. P. Brent, Factorization of the eleventh Fermat number (preliminary report), AMS Abstracts 10 (1989), 89T-11-73.
- 3.
- R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National Univ., Canberra, Feb. 1997. ftp://nimbus.anu.edu.au/pub/Brent/rpb161tr.dvi.gz .
- 4.
- R. P. Brent, Factorization of the tenth Fermat number, Math. Comp., 68 (1999), 429-451. MR 99e:11154
- 5.
- J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of
 ,  up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988. MR 90d:11009 - 6.
- J. P. Buhler, personal communication to Crandall, 1993.
- 7.
- P. Bürgisser, M. Clausen and M. A. Shokrollahi, Algebraic Complexity Theory, Springer-Verlag, 1997. MR 99c:68002
- 8.
- C. Caldwell, The Dubner PC Cruncher - a microcomputer coprocessor card for doing integer arithmetic, review in J. Rec. Math. 25(1), 1993.
- 9.
- D. V. and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), 385-434. MR 88h:11094
- 10.
- R. E. Crandall, Projects in scientific computation, Springer-Verlag, New York, 1994. MR 95d:65001
- 11.
- R. E. Crandall, Topics in advanced scientific computation, Springer-Verlag, New York, 1996. MR 97g:65005
- 12.
- R. Crandall, J. Doenias, C. Norrie, and J. Young, The twenty-second Fermat number is composite, Math. Comp. 64 (1995), 863-868. MR 95f:11104
- 13.
- R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), 305-324. MR 94c:11123
- 14.
- B. Dixon and A. K. Lenstra, Massively parallel elliptic curve factoring, Proc. Eurocrypt '92, Lecture Notes in Computer Science 658, Springer-Verlag, Berlin, 1993, 183-193. MR 94e:94002
- 15.
- H. Dubner and R. Dubner, The Dubner PC Cruncher: Programmers Guide and Function Reference, February 15, 1993.
- 16.
- G. B. Gostin, New factors of Fermat numbers, Math. Comp. 64 (1995), 393-395. MR 95c:11151
- 17.
- J. C. Hallyburton and H. Brillhart, Two new factors of Fermat numbers, Math. Comp. 29 (1975), 109-112.
Corrigendum, ibid 30 (1976), 198. MR 51:5460; MR 52:13599 - 18.
- W. Keller, Factors of Fermat numbers and large primes of the form
 , Math. Comp. 41 (1983), 661-673. Also part II, preprint, Universität Hamburg, Sept. 27, 1992 (available from the author). MR 85b:11117 - 19.
- D. E. Knuth, The art of computer programming, Volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, Menlo Park, CA, 1981. MR 83i:68003
- 20.
- M. Kraitchik, On the factorization of
 , Scripta Math. 18 (1952), 39-52. MR 14:121e - 21.
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319-349. MR 93k:11116
- 22.
- A. K. Lenstra and M. S. Manasse, Factoring by electronic mail, Proc. Eurocrypt '89, Lecture Notes in Computer Science 434, Springer-Verlag, Berlin, 1990, 355-371. MR 91i:11182
- 23.
- H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 89g:11125
- 24.
- P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 88e:11130
- 25.
- P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph. D. dissertation, Mathematics, University of California at Los Angeles, 1992. ftp://ftp.cwi.nl/ pub/pmontgom/ ucladissertation.psl.Z .
- 26.
- P. L. Montgomery, A survey of modern integer factorization algorithms, CWI Quarterly 7 (1994), 337-366. MR 96b:11161
- 27.
- F. Morain, Courbes elliptiques et tests de primalité, Ph. D. thesis, Univ. Claude Bernard - Lyon I, France, 1990. ftp://ftp.inria.fr/INRIA/publication/ Theses/TU-0144.tar.Z MR 95i:11149
- 28.
- A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inf. 1 (1971), 139-144.
- 29.
- J. L. Selfridge, Factors of Fermat numbers, Math. Comp. 7 (1953), 274-275.
- 30.
- J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics 106, Springer-Verlag, New York, 1986. MR 87g:11070
- 31.
- R. D. Silverman and S. S. Wagstaff, Jr., A practical analysis of the elliptic curve factoring algorithm, Math. Comp. 61 (1993), 445-462. MR 93k:11117
- 32.
- H. Suyama, Informal preliminary report (8), personal communication to Brent, October 1985.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
11Y05, 11B83, 11Y55,
11-04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25
Retrieve articles in all Journals with MSC
(1991):
11Y05, 11B83, 11Y55,
11-04, 11A51, 11Y11, 11Y16, 14H52, 65Y10, 68Q25
Additional Information:
R.
P.
Brent
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Email:
Richard.Brent@comlab.ox.ac.uk
R.
E.
Crandall
Affiliation:
Center for Advanced Computation, Reed College, Portland, OR 97202, USA
Email:
crandall@reed.edu
K.
Dilcher
Affiliation:
Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia B3H 3J5, Canada
Email:
dilcher@cs.dal.ca
C.
Van Halewyn
Affiliation:
Department of Computer Science and Engineering, Oregon Graduate Institute
Address at time of publication:
Deutsche Bank AG, London, England
Email:
Christopher.van-halewyn@db.com
DOI:
10.1090/S0025-5718-00-01207-2
PII:
S 0025-5718(00)01207-2
Keywords:
Discrete weighted transform,
DWT,
ECM,
elliptic curve method,
factorization,
Fermat number,
$F_{13}$,
$F_{15}$,
$F_{16}$,
integer factorization
Received by editor(s):
July 29, 1997
Posted:
March 1, 2000
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org