philmoore
08-08-2007, 03:22 PM
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.
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.