Geoffrey Faivre-Malloy writes:
I found another factor for Fermat 16. What do I do now? How can I
factor this number that I found? Are there programs out there that
will let me do that?
Yes, there are such programs. One is ecmfactor, a program I maintain
as part of the mers package at:
http://www.garlic.com/~wedgingt/mers.tar.gz
mers.tgz
(two file names with the same contents). Ecmfactor uses the Elliptic
Curve Method algorithm in the freeLIP library (written in C by Arjen
Lenstra and presently maintained by Paul Leyland). If freeLIP
compiles using your compiler, than ecmfactor should run fine.
FYI, the factor is:
M16384 has a factor:
3178457030898592746194675570663374420833971377365687459461386297851584459031
8073180374859604847822828243686877928403667633015295
I've appended the output from ecmfactor on this number.
Also, Steven Whitaker is quite correct; M16384 is, usually at least,
used to denote 2^16384 - 1, which is a Mersenne number. Fermat
numbers are of the form 2^(2^n) + 1. However, since 16384 is a power
of two, this particular Mersenne number, as Steven also notes, is
related to the Fermat numbers, since:
2^(2*x) - 1 = (2^x)^2 - 1^2 = (2^x - 1)*(2^x + 1)
(using the usual difference of squares method to get the two factors).
Since 16384 is a power of two, this can be repeated several times on
the 2^x - 1 half to get the factors that Steven lists.
And, if you at all interested in prime numbers and factoring, then
I strongly second Steven's suggestion of reading Chris Caldwell's
web pages at:
http://www.utm.edu/research/primes/index.html
Will
Ecmfactor says:
% ecmfactor -d < M16384.factor
prime factor: 3
prime factor: 5
prime factor: 17
prime factor: 257
new cofactor is composite
factor: 641
prime factor: 641
new cofactor is composite
factor: 114689
prime factor: 114689
new cofactor is composite
factor: 4179067011073
factor of factor: 65537
prime factor: 63766529
new cofactor is composite
factor: 26017793
prime factor: 26017793
new cofactor is composite
factor: 274177
prime factor: 274177
new cofactor is composite
factor: 974849
prime factor: 974849
new cofactor is composite
factor: 319489
prime factor: 319489
new cofactor is composite
factor: 6700417
prime factor: 6700417
new cofactor is composite
factor: 2424833
prime factor: 2424833
new cofactor is composite
tried 1 curves at bound 100 without success
tried 1 curves at bound 105 without success
tried 1 curves at bound 110 without success
tried 1 curves at bound 115 without success
tried 1 curves at bound 120 without success
tried 1 curves at bound 125 without success
tried 1 curves at bound 130 without success
factor: 45592577
prime factor: 45592577
new cofactor is composite
tried 1 curves at bound 135 without success
tried 1 curves at bound 140 without success
tried 1 curves at bound 145 without success
tried 1 curves at bound 150 without success
tried 1 curves at bound 155 without success
tried 1 curves at bound 161 without success
tried 1 curves at bound 167 without success
tried 1 curves at bound 173 without success
tried 1 curves at bound 179 without success
tried 1 curves at bound 185 without success
tried 1 curves at bound 191 without success
tried 1 curves at bound 197 without success
tried 1 curves at bound 203 without success
tried 1 curves at bound 209 without success
tried 1 curves at bound 215 without success
tried 1 curves at bound 221 without success
tried 1 curves at bound 227 without success
tried 1 curves at bound 233 without success
tried 1 curves at bound 239 without success
tried 1 curves at bound 245 without success
tried 1 curves at bound 252 without success
tried 1 curves at bound 259 without success
tried 1 curves at bound 266 without success
tried 1 curves at bound 273 without success
tried 1 curves at bound 280 without success
tried 1 curves at bound 287 without success
tried 1 curves at bound 294 without success
tried 1 curves at bound 301 without success
tried 1 curves at bound 308 without success
tried 1 curves at bound 315 without success
tried 1 curves at bound 322 without success
tried 1 curves at bound 329 without success
tried 1 curves at bound 336 without success
tried 1 curves at bound 343 without success
tried 1 curves at bound 350 without success
tried 1 curves at bound 358 without success
factor: 190274191361
prime factor: 190274191361
new cofactor is composite
tried 1 curves at bound 366 without success
tried 1 curves at bound 374 without success
tried 1 curves at bound 382 without success
tried 1 curves at bound 390 without success
tried 1 curves at bound 398 without success
tried 1 curves at bound 406 without success
tried 1 curves at bound 414 without success
tried 1 curves at bound 422 without success
tried 1 curves at bound 430 without success
tried 1 curves at bound 438 without success
tried 1 curves at bound 446 without success
tried 1 curves at bound 454 without success
tried 1 curves at bound 462 without success
tried 1 curves at bound 470 without success
tried 1 curves at bound 478 without success
tried 1 curves at bound 486 without success
tried 1 curves at bound 495 without success
tried 1 curves at bound 504 without success
tried 1 curves at bound 513 without success
tried 1 curves at bound 522 without success
tried 1 curves at bound 531 without success
tried 1 curves at bound 540 without success
tried 1 curves at bound 549 without success
tried 1 curves at bound 558 without success
tried 1 curves at bound 567 without success
tried 1 curves at bound 576 without success
tried 1 curves at bound 585 without success
tried 1 curves at bound 594 without success
tried 1 curves at bound 603 without success
tried 1 curves at bound 612 without success
tried 1 curves at bound 621 without success
tried 1 curves at bound 630 without success
tried 1 curves at bound 639 without success
tried 1 curves at bound 649 without success
tried 1 curves at bound 659 without success
tried 1 curves at bound 669 without success
tried 1 curves at bound 679 without success
tried 1 curves at bound 689 without success
tried 1 curves at bound 699 without success
tried 1 curves at bound 709 without success
tried 1 curves at bound 719 without success
tried 1 curves at bound 729 without success
tried 1 curves at bound 739 without success
tried 1 curves at bound 749 without success
tried 1 curves at bound 759 without success
tried 1 curves at bound 769 without success
tried 1 curves at bound 779 without success
tried 1 curves at bound 789 without success
tried 1 curves at bound 799 without success
tried 1 curves at bound 809 without success
tried 1 curves at bound 819 without success
tried 1 curves at bound 830 without success
tried 1 curves at bound 841 without success
tried 1 curves at bound 852 without success
tried 1 curves at bound 863 without success
tried 1 curves at bound 874 without success
tried 1 curves at bound 885 without success
tried 1 curves at bound 896 without success
tried 1 curves at bound 907 without success
tried 1 curves at bound 918 without success
tried 1 curves at bound 929 without success
tried 1 curves at bound 940 without success
tried 1 curves at bound 951 without success
tried 1 curves at bound 962 without success
tried 1 curves at bound 973 without success
tried 1 curves at bound 984 without success
tried 1 curves at bound 995 without success
tried 1 curves at bound 1006 without success
tried 1 curves at bound 1017 without success
tried 1 curves at bound 1028 without success
tried 1 curves at bound 1039 without success
tried 1 curves at bound 1051 without success
factor: 1256132134125569
prime factor: 1256132134125569
new cofactor is composite
tried 1 curves at bound 1063 without success
tried 1 curves at bound 1075 without success
tried 1 curves at bound 1087 without success
tried 1 curves at bound 1099 without success
tried 1 curves at bound 1111 without success
tried 1 curves at bound 1123 without success
tried 1 curves at bound 1135 without success
tried 1 curves at bound 1147 without success
tried 1 curves at bound 1159 without success
tried 1 curves at bound 1171 without success
tried 1 curves at bound 1183 without success
tried 1 curves at bound 1195 without success
tried 1 curves at bound 1207 without success
tried 1 curves at bound 1219 without success
tried 1 curves at bound 1231 without success
tried 1 curves at bound 1243 without success
tried 1 curves at bound 1255 without success
tried 1 curves at bound 1267 without success
tried 1 curves at bound 1279 without success
tried 1 curves at bound 1292 without success
tried 1 curves at bound 1305 without success
tried 1 curves at bound 1318 without success
tried 1 curves at bound 1331 without success
tried 1 curves at bound 1344 without success
tried 1 curves at bound 1357 without success
tried 1 curves at bound 1370 without success
factor: 67280421310721
prime factor: 67280421310721
cofactor is prime or a strong pseudo-prime
cofactor: 59649589127497217
So some of the factors that Steinar listed are composite, as he noted
was likely. All the numbers printed as 'prime factor's by ecmfactor
_might_ be merely strong pseudo-primes, to base-3 and four other,
random, bases greater than 2, but the odds are very much in favor of
them each being prime.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
