On Thursday 02 September 2004 22:56, olivier latinne wrote: > > . I have a program that make very fast divisions: for a divisor > less than 2^63, I can made a single division of a Mersenne > number with p of 1000 billion (10^12) in about 100 hours on > one CPU of a SGI Origin 3400.
The code in mprime/Prime95 manages to do the "single division" for p up to ~ 80 million in something of the order of one microsecond on a 1 GHz PIII. (i.e. ~ 11.6 decimal orders of magnitude faster than your claim). I doubt the performance of an SGI Origin 3400 CPU is that much slower than a Pentium! Increasing p to ~ 4 billion (2^32) would increase the run time but not hugely as the run time sensitivity of the code to p is logarithmic. Going past 2^32 would involve a significant coding change to deal with what a 32-bit CPU has to work as "double length" integers but the run time would not double until p approached 2^64. The problem is that there are such a large amount of possible divisors to eliminate - even after screening out those that are "obviously" composite and those where k (in 2kp+1) has the wrong residue modulo 8. If you have an understandable theory that eliminates a significant proportion of remaining candidate factors without a proportionate increase in trial factoring run time, let's hear about it. If you have a theory that allows one to identify Mersenne primes for p as small as ~20 million without considering factors greater than 2^63, well, frankly, as an amateur mathematician I'd be astonished. In fact, a heuristic argument would run that, for p>2^63, all prime-exponent Mersenne numbers would have to be either prime or composite (since the smallest possible factor would be greater than your limit); the known existence of Sophie Germaine primes > 2^63 would then invalidate the chance of primality, leading to the conclusion that the set of Mersenne primes has a largest member and is therefore finite in size, in contradiction to generally accepted arguments. Astonish me. Please. Regards Brian Beesley _______________________________________________ Prime mailing list [EMAIL PROTECTED] http://hogranch.com/mailman/listinfo/prime
