Spike Jones <[EMAIL PROTECTED]> comments;
--------------953E7B41754C35108B97B346
> Nathan I liked your comment about the largest genuine composite:
> a number known to be composite but for which none of the factors
> are known. I suppose we could set up a computer to arbitrarily
> generate a few million 20 digit primes by factoring, then multiply
> them all together to get the largest known composite number for
> which none of the factors would be "known", eh? spike
Knowing that the product is composed of 20-digit
primes, it can be broken by ECM.
If the product has 100 million decimal digits (330 million bits),
then we need 41 megabytes per residue.
ECM step 1 with homogeneous coordinates needs about 6-10 such residues,
so 1 Gb is more than adequate even with temporaries for FFT code.
The first GCD will reveal several of the factors --
how many depends upon the step 1 limit.
Perhaps one finds an 8-million-digit factor and a 92-million-digit cofactor.
Both of these can be fed back into the algorithm
(recursively) until the original number is completely factored.
This computation can be partially parallelized. Perhaps 30 machines
each get two factors, around 8 million digits and 92 million digits.
Using results from two machines, we get four factors, about
640000, 7360000, 7360000, 84640000 digits.
After incorporating results from all 30 machines,
the largest factor (where all curves were unsuccessful)
will be about 10^8 * (23/25)^20 ~- 8.2 million digits.
Spike's idea, with 50-digit or 100-digit primes rather than
20 digits, will give hard-to-factor numbers using today's
Are there any large known composite numbers c
for which we know a (not necessarily prime) factor of 2^c - 1 but not of c?
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
