----- Original Message -----
From: Eric Hahn <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Thursday, August 05, 1999 9:05 AM
Subject: RE: Mersenne: Multiple residues - enhancing double-checking
>
> The only thing this scheme would accomplish is to
> allow a third test to begin (if a mismatch is found
> somewhere along the way) before the second one
> finishes. If the third test did match the first,
> there would be savings in discarding the second.
This thought may sound awfully like poaching, but here goes anyway...
Some folks want to do first time LL tests. Some folks ask for best suited
tasks -- I do.
If I have a machine doing double-checks I really do not know or care if it
happens to start the double-check
the same day as the first time LL test starts. Primenet can track if I am
the first LL or the check LL.
If the check finishes before the first LL on a prime Mp, George will need to
set the rules. Perhaps both
parties get co-discoverer status rather than discoverer status. This could
make concurrent double-checking
a lot more attractive. Concurrent double checking might speed up some of
the activities, especially finding the
need for triple checks.
>Current trial-factoring saves 12.5% of the total time
>that would be spent without any trial-factoring.
>
>If we were to trail-factor to say, 2^70 (which should
>cause factor time to increase to 1 month), without any
>additional improvement to exponents being factored this
>will cause a drop to about 8.8% overall time saved.
Another thought: does the factor test already use Goldbach's conjecture?
Someone with more cleverness and time than I have right now might think
about using this fact:
Given p,q integers and r = p+q. Then Mr = Mp.Mq + Mp + Mq
This is just: Mp.Mq = (2^p - 1)(2^q - 1) = 2^(p+q) - 2^p - 2^q + 1 = Mr -
Mp - Mq
So what, right? Suppose we want to factor test Mr. We can (by trial and
error) find
primes p and q with r = p+q. Usually there are lots. (Hey, if we don't
then we just found
a counterexample to Goldbach's conjecture. That would be big news, too.)
Mr, Mp and Mq are relatively prime in pairs, so none of the factors of Mp or
Mq divide Mr.
Now, if F is a test factor in the range, suppose we keep a database of Fp =
Mp mod F. This is big,
but once we have r=p+q, we just calculate Fp.Fq + Fp +Fq mod F. If 0, then
F divides Mr.
One practical question is how bloody big is this collection of Fp's?
Could this make test factoring run faster?
Joth
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
