Foghorn Leghorn writes:
Second, I see that there are now some composite exponents in the
ECM factoring page. Why are none of them even? Is there a technical
reason that makes them less interesting?
As Sam Laur and George Woltman have mentioned, even exponent Mersennes
are always composite. George also pointed out the explicit factorization
based on the usual difference of squares rule:
x^2 - y^2 = (x - y)*(x + y)
which, for our current purposes, gives:
M(2*n) = 2^(2*n) - 1 = (2^n)^2 - 1^2 = (2^n - 1)*(2^n + 1)
= M(n)*(M(n) + 2)
So, if you want to know the factors of M(2*n), then factor M(n) and
M(n) + 2 == 2^n + 1. Thus, (part of) the Cunningham Project tries to
factor '2-' and '2+' numbers, 2^n - 1 for odd n and 2^n + 1 for all n.
To fully understand the Cunningham Project 2+ file, there's another
"algebraic factorization" that works for 2+ numbers for certain n's:
2^(4*a - 2) + 1 = (2^(2*a - 1) - 2^a + 1)
*(2^(2*a - 1) + 2^a + 1)
The first column of the 2+ file for the lines that can be factored in
this was is n = 4*a - 2. For example, here are a couple of early
lines in 2+:
14L 113
14M 29
2^14 + 1 = 16385 = 5*29*113
where 14 = n = 4*a - 2, giving a = 4. So:
2^14 + 1 = 2^(4*4 - 2) + 1 = (2^(2*4 - 1) - 2^4 + 1)
*(2^(2*4 - 1) + 2^4 + 1)
= (2^7 - 16 + 1)*(2^7 + 16 + 1)
= (128 - 15)*(128 + 17)
= 113*145
= 113*5*29
5 will always appear in this complete factorization if n is even,
since M(4) = 15 and 5 divides no smaller Mersenne number (3 also
always appears, but in the Mersenne (2-) half when n is even, in this
case 2^14 - 1 = 16383 = 3*43*127 = 129*127 where 127 is, of course,
2^7 - 1 == M(7)).
Paul Leyland maintains the Cunningham Project data, presently at both
of ftp://ftp.cam.uk.eu.microsoft.com/pub/math/cunningham/ and
ftp://sable.ox.ac.uk/pub/math/cunningham/.
George Woltman continued:
However, prime95 can be used on even exponents. If both 2^n-1 and
2^n+1 have not been fully factored then you can modify your
lowm.txt file and try factoring 2^2n-1. If one of the two smaller
values has been factored, then you are better off factoring either
2^n-1 or waiting for an upgrade that can factor numbers of the form
2^n+1.
The beta mers package version of ecm3 can also now handle even
exponent Mersenne numbers, including, imperfectly, the L and M
"halves" described above when the exponent is 8*a - 4 == 2*n. The
program knows enough to split the halves into distinct numbers to
factor, but does not yet distinguish, in the output, to which half a
new factor belongs. Old "factors", from the input, are checked
against both halves before being rejected as incorrect (if it divides
neither half).
Ecm3 also handles composite (including even) exponent Mersennes
slightly better than Prime95 by pulling out factors that are due to
smaller Mersennes (with exponents that factor the larger, composite
exponent) before trying to factor what's left. For even exponent
(2*x) Mersennes, this means that ecm3 only works on the 2^x + 1 part;
the rest is ignored by ecm3 since it will be or already has been
factored independently as M(x) == 2^x - 1. Prime95's much greater
speed, due to the FFT multiplication, is thus at least partially
offset in that ecm3 is trying to factor smaller numbers - often _much_
smaller - when the exponent is composite. At least until George
decides to improve Prime95 in this way.:)
Further, since ecm3 can now handle even exponents, my data files,
including lowM.txt, will now include data for even exponents. I have
already added the data from the Cunningham Project's 2+ file and will
update my web site's mersdata.zip and mersdata.gz data files within a
day or so, after I check some details of my new update scripts and the
newest version of ecm3.
Lastly, feel free to send me data related to composite exponent
Mersenne numbers; it will get added as I have time, as for the prime
exponents. Note that the mers package trial factorers still only work
for prime exponents; the sieving code needs to be substantially
modified to deal with composite exponents. I will almost certainly
not cure this defect any time soon, since ECM and P-1 are much faster
than trial factoring, _especially_ for these smaller exponents.
Will
