From: "Peter L. Montgomery" Subject: Re: Factoring a certain 217 digit composite. Date: Fri, 31 Mar 2000 05:05:33 GMT Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math Summary: [missing] [Follow-up to sci.math only.] In article <8bvr37$v84$1@nnrp1.deja.com> Bob Silverman writes: >In article <38E2604C.CB3AA520@stat.fsu.edu>, >George Marsaglia wrote: >> A certain promising random number generator is based on the >> prime p=2^2203-1. The period of the generator >> is the order of 2^32 for that prime, and to get it I need >> the factors of (p-1)/2 = (2^1101-1)(2^1101+1). >> >> The factors of 2^1101-1 are known, >> >> but for 2^1101+1, only the factor 28627 seems to be known, >> leaving a composite of 217 digits. >> >> Can anyone provide factors for (2^1101+1)/28627, >> >> or suggest to the various factoring groups that >> such a factorization might lead to an interesting and useful result? > >Hi George, > >This number is in fact within reach of the Special Number Field with >a very large, but not super massive effort. > >However, nowadays it seems that everyone is chasing Mersenne primes. >(big bucks have been offered for the first 10 million digit prime) > >I have *tried* to get volunteers to help run NFS, without success. >I have tried to encourage people to help out with running ECM on >2^n + 1 without (much) success. > >I would be happy to provide you code (and technical assistance) if you >want to organize an effort to do this number. 2,1101+ is one of many entries in the Cunningham project, managed by Sam Wagstaff. Read about this project at http://www.cerias.purdue.edu/homes/ssw/cun/index.html If you want to contribute to this project, you can use ECM (Elliptic Curve Method) or NFS (Number Field Sieve). ECM finds individual factors of a large number when the factors are `small'. When ECM was discovered in 1985, early implementations found hundreds of previously unknown 11- to 20-digit factors of Cunningham numbers. Nowadays most new factors are 35 digits or more. The record factor size is 54 digits (53 digits for Cunningham factors). If you want to run ECM, join ECMNET, managed by Paul Zimmermann: http://www.loria.fr/~zimmerma/records/ecmnet.html NFS factors a large number in time dependent upon the size of the input number, not the size of its factors. The record size is 211 digits when the number has special form [R211 = (10^211 - 1)/9 has 93- and 118-digit prime factors]. When the number lacks special form, the record is 155 digits (512 bits!) If you want to run NFS, join NFSNET, managed by Conrad Curry: http://orca.st.usm.edu/~cwcurry/nfs/nfs.html There is a political difference between ECM and NFS. If you run ECM and find a factor, you get full credit for it. If you run NFS, you contribute data to a central site -- when the central site accumulates enough data, it factors the number, and all contributors share the credit. ECM is an individual effort; NFS is a group effort. The 217-digit cofactor of 2,1101+ divides 2^734 - 2^367 + 1, about 11 digits more than the record 10^211 - 1. It is certainly feasible to do this by NFS, but I believe there is greater interest in 2^727 - 1, which has no known factors. Now is the time, however, for someone to mount an intensive ECM attack on the 217-digit cofactor. With luck, ECM might find a 49-digit factor and leave a prime cofactor, completing the task. -- E = m c^2. Einstein = Man of the Century. Why the squaring? Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California Microsoft Research and CWI