On 13 May 2001, at 20:06, [EMAIL PROTECTED] wrote:
> True, for composite c, not all factors of 2^c - 1 need have form
> 2.K.c + 1; for example, if c = 15, 2^c - 1 = 7.31.151, and the
> smallest factor, 7, does not have the form 2.K.15 + 1. However,
> if we do not know any of the factors of c, the best we can reasonably
> do is to search for factors of the form 2.K.c + 1, which we can do
> without knowing any of the factors of c.
Yes.
>
> For c sufficiently large, even sieving for factors of this form
> becomes prohibitively expensive - take your own favorite composite
> lacking known factors, c = 2^33219281-1. Checking if the smallest
> eligible candidate factor 2.K.c + 1 divides C = 2^c - 1 would need
> roughly 33219281 squarings modulo the candidate factor, and since
> that is not of special form (e.g. Mersenne or generalized Fermat)
> each squaring modulo the trial factor will be more than twice as
> expensive as a squaring modulo c.
Yes, I did point out in my original message on this subject that
testing a single factor of M(M(p)) involves about as much effort as
running a LL test on M(p). Actually the squaring need not be much
more expensive as it is possible to combine squaring and modulo
reduction for "Proth" numbers using DWT in much the same way as is
done for Mersenne numbers, and 2kM(p)+1 is going to be a Proth number
for all reasonable values of k once p is any size at all.
> On the other hand, if c itself
> has a smallest factor so large as to make finding it practically
> impossible, then indeed it may prove easier to find a "small"
> (in the sense that K is small) factor of 2^c - 1 than of c. By
> its very nature such a factor would not help one in factoring
> c itself.
Do you mean you can prove that last sentence, or do you just mean
we're all so stupid that we haven't found out how to, yet?
>
> I'm not sure what point you're trying to make with the K > k^x
> condition - do you mean to ensure that if k is large (which it
> must be if c has undergone a sufficient amount of trial factoring),
> K also will be?
Yes. If we know that e.g. k>10^40 and we can prove that e.g. K>k^0.1
then we know K>10000. Maybe _much_ bigger. Which implies (even after
sieveing out those values of K for which 2KM(p)+1 itself has a small
factor, or is congruent to 3 or 5 modulo 8) the work involved in
finding that factor is at least thousands of times greater than the
work involved in LL testing M(p). In other words, given current
hardware, it really is a waste of time, for p ~ 10^6.
Conversely, if there is no such limit on x, then we _could_ be lucky
and find a factor with a very small K. In fact, given the
distribution of factors of Mersenne numbers (even ignoring the
special case where p is a 3 mod 4 Sophie Germain prime), it is rather
more probable that we _will_ find a factor in a fixed size interval
when K is small than it is when K is large.
My gut feeling is that there is some limit, i.e. if k is large then K
will be large too. However, formal proofs and heuristic arguments
both seem to be vanishingly thin on the ground.
>
> Perhaps one should simply exclude such constructions by defining
> a "genuine composite" as a number which has been shown
> to be composite by direct (nonfactorial) means, e.g. Lucas-Lehmer,
> Pe'pin, Proth or any other rigorous compositeness test, and which
> has no known factors.
Yes. Otherwise the very question of "what is the largest known
composite with no known factors" has no meaning.
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
