I would like to propose a modest modification of the Seventeen or Bust client. Currently, the client does PRP (probable prime) tests on candidates that have survived sieving and, in some cases, P-1 factoring. In the overwhelming majority of cases, the test returns a verdict of composite. In the rare case that a test says that the number is a probable prime, a full primality test is then run using Yves Gallot's program Proth.exe. The odds of a huge probable prime turning out to not be actually prime are remotely small, though not zero, and to my knowledge, every case of a probable prime so far has checked out. However, Louie tells me that Gallot's program takes approximately 4 times as long to run as the client, which explains why the last prime was confirmed so long (about 40 days) after the initial discovery.
Here is how the probable prime test works, to check whether q = k*2^n+1 is probably prime: Pick a base, I believe that the client always uses 3. (Can anyone confirm this?) Raise 3 to the power q-1 mod q, i.e., raise 3^(k*2^n) mod q. This can be done by first computing 3^k and then squaring the result n times, mod q. If the result is 1, you have a probable prime. If the result is not 1, you have a definite composite.
Here is how the Proth test works, to check whether q = k*2^n+1 is an actual prime, given k < 2^n: Pick a quadratic non-residue for the base. Because q is congruent to 1 mod 4 for n>1, quadratic reciprocity tells us that the base 3 is a non-residue as long as k is not divisible by 3 and also q is not divisible by 3. If q were divisible by 3, it would have been eliminated in the very first stage of the sieve, and we wouldn't be testing it. All values of k divisible by 3 were eliminated at low values of n, so for all the values being searched by Seventeen or Bust, we can use the base 3. Now raise 3 to the power (q-1)/2 mod q, i.e. raise 3^(k*2^(n-1)) mod q. If the result is -1 (equivalent to q-1), then q is prime. If the result is not -1, then q is composite.
Note that the Proth test does the exact same calculation as the PRP test, but with one less squaring at the end, and a comparison to -1 rather than +1. My suggestion is to do the Proth test first. Then, if we find a prime, we have at least one indication that the number is a genuine prime while we await a verifcation on other software. However, the data-base currently stores the low order bits of the residue from the PRP test, so if the result is not -1, square the result one more time so that the residue of the PRP test can be reported, keeping the data-base consistent with current usage. If some composite turns out to have a residue of 1, then we will have discovered a truly rare mega-digit pseudo-prime!
Granted, this would only have saved 40 days of waiting before we knew whether the probable prime is a genuine prime, and only for those in the loop about the original discovery, but it seems like a fairly simple change to make. For a ten million digit prime, the 40 days will become more like 250 days, so as the confirmations take longer and longer, it would be nice to at least be able to confirm a discovery with a re-run on the client itself. I believe that Jean Penne's LLR also can do a full Proth test, but as it makes use of George Woltman's routines, it can't be considered a fully independent verification in the same way as one run with Proth.exe.
I'm sorry to say it but i think it's very amibitious to except any updates to the client, there has been much talk of new versions and changes and upgrades but there has been no visible progress for several years now. I'm hoping to be proved wrong and a fancy new version of the client will be released tomorrow, but i think it's unlikely!
Would PFGW be faster at verification?
How is Jean Penne's LLR "not independent", but a re-run on the client itself is?! The only advantage of having the client perform Proth Test is that you don't need a second test before submitting to Top 5000 page (since submitting PRPs are not considered good form there).Originally Posted by philmoore
Frankly they should just use LLR's proth test for reverification and be done with it. Or use PFGW's N-1 test.
Clarification: A re-run on the same client would certainly not be an independent verification, only a verification that the software seemed to be working correctly. I don't know for sure, but I suspect that pfgw and LLR would both be able to perform a full Proth test in about the same time that the client performs a prp test, as all three use George's multiplication routines. Whether Chris Caldwell would accept verifications on pfgw and LLR as independent is a question we would have to ask him.
The Top 5000 list doesn't require any primes to be "independently verified". It only insists that the prime be proven and not a PRP. So, while a PRP test is not good enough, a proth test is (independent or not).
Here is a suggestion for two separate verifications via a Proth test that a candidate is prime, both potentially using the same multiplication routines, but computing a different series of residues:
1) Compute 3^k mod q. Call the result R, and now compute R^(2^(n-1)) mod q. If the final result is -1 mod q, then q is prime.
2) Compute 3^(2^(n-1)) mod q. Call the result S, and now compute S^k mod q. If the final result is -1 mod q, then q is prime.
Either of these could be done easily using pfgw and a simple SCRIPT file. If LLR uses the first computation, use pfgw to do the second. Both verifications should complete in about the same amount of time. Because the project does not want to announce an unverified result anyway, this would provide solid verification in the shortest possible time, and the client wouldn't even need to be modified.
Am I missing something here? Can't you use the -tm option with PFGW? That should perform a primality test on numbers of the form k*2^n+1.
You are correct. Jim Fougeron also tells me that the development version 20050428 allows doing a strong probable-prime (i.e., Miller-Rabin) test to the base 3 with the following syntax:
pfgw -bm3 -f0 -q(expression)
For the Proth primes discovered by Seventeen or Bust, a Miller-Rabin test to base 3 is the same as a Proth test, and proves primality, not just probable primality. The only problem is that the latest development version available at openpfgw is 20050213. Does anyone know how to get ahold of 20050428 ?
The point of my last post was that, given a probable prime, we can run two different verifications of primality simultaneously using different computations, even though both verifications make use of George Woltman's routines. That should allow SoB to confidently announce the discovery of the next prime without the necessity of waiting for a verification from Proth.exe.
That makes perfect sense, although I know of at least one person who would claim that George's code is buggy and can't be trusted...
Posting Permissions
Reply With Quote