Brian Beesley comments:
> Just out of interest, did anyone ever try Fermat's Method on some of
> the "tougher" numbers in the Cunningham tables ... Fermat's Method
> can be speeded up by a large factor since we _know_ the form of the
> factors - of course, it's still going to fail to find factors in a
> reasonable time unless a pair of factors of very similar size do, in
> fact, exist. Also, any factors found would not neccessarily be prime,
> though cracking the two "halves" ought to be easier than tackling the
> whole.
D.H. Lehmer did some cofactors this way. The largest seems to be
the 33-digit number (2^109 - 2^55 + 1)/5, otherwise known as 2,218L.
See the history pages in the book `Factorizations of b^n +- 1,
b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers'
by John Brilhart et al.
The Continued Fraction method, introduced in the late 1960's,
generalized Fermat's method and made the difference of squares method obsolete.
The P-1 method accelerated this gap. Today it takes under a second
to factor 2,218L by P-1.
Montgomery factorization program. Compiled Tue Jun 3 21:25:54 MET DST 1997.
Allows inputs up to about 6300 decimal digits.
C(2,218L)
Composite cofactor has 33 digits:
129807421463370683507503004437709
RAND_PRINT - Current random number seed is 198181203 271851921 233382925
C(2,218L) p-1 method found divisor near p= 7603
74323515777853
CHEK - Nontrivial GCD p-1
74323515777853
The first number below is the product of the second and the third, as found
by p-1 after 18285 multiplies and GCDs
in 0.05 CP seconds at Wed Jul 14 16:52:44 1999
129807421463370683507503004437709
74323515777853
1746518852140345553
Probable prime cofactor has 19 digits -- terminating.
One instance of Fermat's method remains important --
factoring p^2 where p is prime.
Peter Montgomery
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
