Brian Beesley wrote: > If someone could merely demonstrate that, if the smallest factor of > c = 2^p-1 is 2kp+1 for some k, C = 2^c-1 and the smallest factor of > C with the form 2Kc+1 is 2Kc+1 for some K, then K > k^x for some > x > 0, this would show that searching for factors of C without > knowledge of factors of c is probably _unlikely_ to be successful. 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. 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. 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. 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? 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. -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
