I'm catching up on sveral months' worth of digests, so some of
this has been covered by others.
On 23 April 2001, Brian J. Beesley wrote:
> AFAIK the largest number currently known to be composite but with no
> known factors is 2^33219281-1, the only 10 million digit Mersenne
> number which has been LL tested twice with matching final residual.
> (Rick Pali, 2000 & Brian Beesley, 2001) This number has been trial
> factored up to 2^68 and subjected to P-1 with B1=495000.
Ah, but if C is composite with no known factors, so is 2^C - 1.
Or, to paraphrase the famous poem about the wee beasties:
People brag about huge composites C,
And hope none larger will smite 'em,
But then 2^C - 1 is composite, too,
And so on, ad infinitum.
Hans Riesel made the same point in his reply of 26 Apr 2001, to which
Brian replied:
> It is certainly true that, for composite c, 2^c-1 is composite. It
> does _not_ follow that no factors of 2^c-1 are known - even if c is
> itself a Mersenne number.
OK, so what factors of 2^C - 1 are known, for C = 2^33219281-1 ?
Now it is possible that for C composite and f the smallest factor
of C (known or not), 2^C - 1 may in fact have a smaller factor than
2^f - 1 (more on this below), but for C sufficiently large, it will
nearly always be more difficult to find a factor of 2^C - 1 than of C,
if for no other reason that arithmetic modulo C will be much cheaper
than arithmetic modulo the much larger 2^C - 1.
Please don't think that I'm picking on Brian - Crandall, Papadopoulos
and I made similar claims about F24 being the largest genuine composite
at the time we completed our machine proof of that number, and were
similarly put in our place by one of the reviewers of the resulting
manuscript.
On 28 Apr 2001, Peter Montgomery wrote:
> Show us how the factors
>
> 131009 of M_(M11) = 2^(2^11 - 1) - 1
> 724639 of M_(M11)
> 285212639 of M_(M23)
>
> lead to factorizations of M11 and M23.
As Peter well knows, if C = a.b, then (2^a - 1) and (2^b - 1)
are factors of (2^C - 1), but there will generally be other factors
of (2^C - 1), too. The above are examples of these "other factors"
and as such don't help us find factors of 2^11 - 1. But the factor
8388607 = (2^23 - 1) of M_(M11) does lead to a factor of M11, as does
618970019642690137449562111 = (2^89 - 1).
Of course if C has no small factors, finding factors of the special
form (2^a - 1) will be much more difficult (in general) than finding
smaller factors not of this special form, thus attempting to factor
2^C - 1 in order to factor C would seem rather foolish.
-Ernst
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
