Greenbank
06-29-2005, 11:22 AM
I've been implementing my own sievers, proth_tests and composite tests to help me understand this problem in more detail.
I've been using the GMP library on non x86 hardware (otherwise I'd be using those machines for SoB!).
There are 39278 odd k values between 1 and 78555 (inclusive) and in the last 7 days I've managed to find n's for all but 60 of these candidate k values (excluding the 17 being tested by SoB) that pass a proth-test and prove primality.
My goal is to produce a list of all odd k values < 78557 (excluding the SoB 17) along with the corresponding n value that produces the prime (with the appropriate a value for the proth test).
I've tested up to n=25000 (it's currently testing the 25000 to 26000 range where it has found k=7651,n=25368 and k=38569,n=25562 as prime). Still another 230 tests to go for this range.
Anyone know how high (n) you have to check to get rid of all k-values apart from the original 17? Not looking for actual numbers (don't want to spoil my work) but just a general idea.
I'm doing the following:-
1. A naive sieve to remove all k,n pairs which have a factor between 3 and 10M. This reduces the 1000 n-values down to roughly 11 per k-value.
2. Followed by prime testing with gmp's mpz_probab_prime_p() function.
The mpz_probab_prime_p() function returns one of 3 values. Definitely composite = remove k,n pair from list. Definitely prime (it never returns this). Probably prime. This is better than some of the other prime testing functions as there is no possibility (however slim) of a prime being returned as 'Definitely composite'.
If I get a Probably Prime then I perform a proth-test on it (with a=3). So far the proth_test with a=3 has never failed to prove primality for a number that mpz_probab_prime_p() says is probably prime. If it does fail I will retest with other values of a (5,7,11, etc) but I doubt this will ever happen.
The proth test code is very naive again. It's simply compute N=k*2^n+1, then a^((N-1)/2) mod N using the mpz_powm() function.
I have a much faster siever (based on iterating 2r-1 on the remainder rather than trial division) but I haven't tested it enough to be 100% confident in it.
Once I do some final testing on my new siever I'll be able to sieve to a higher n in the same time period and therefore remove more candidate k,n pairs.
I'm also approaching the point where mpz_probab_prime_p() takes almost as long as doing the proth test directly. Not sure what I'll do when it becomes too much of a burden.
I've been using the GMP library on non x86 hardware (otherwise I'd be using those machines for SoB!).
There are 39278 odd k values between 1 and 78555 (inclusive) and in the last 7 days I've managed to find n's for all but 60 of these candidate k values (excluding the 17 being tested by SoB) that pass a proth-test and prove primality.
My goal is to produce a list of all odd k values < 78557 (excluding the SoB 17) along with the corresponding n value that produces the prime (with the appropriate a value for the proth test).
I've tested up to n=25000 (it's currently testing the 25000 to 26000 range where it has found k=7651,n=25368 and k=38569,n=25562 as prime). Still another 230 tests to go for this range.
Anyone know how high (n) you have to check to get rid of all k-values apart from the original 17? Not looking for actual numbers (don't want to spoil my work) but just a general idea.
I'm doing the following:-
1. A naive sieve to remove all k,n pairs which have a factor between 3 and 10M. This reduces the 1000 n-values down to roughly 11 per k-value.
2. Followed by prime testing with gmp's mpz_probab_prime_p() function.
The mpz_probab_prime_p() function returns one of 3 values. Definitely composite = remove k,n pair from list. Definitely prime (it never returns this). Probably prime. This is better than some of the other prime testing functions as there is no possibility (however slim) of a prime being returned as 'Definitely composite'.
If I get a Probably Prime then I perform a proth-test on it (with a=3). So far the proth_test with a=3 has never failed to prove primality for a number that mpz_probab_prime_p() says is probably prime. If it does fail I will retest with other values of a (5,7,11, etc) but I doubt this will ever happen.
The proth test code is very naive again. It's simply compute N=k*2^n+1, then a^((N-1)/2) mod N using the mpz_powm() function.
I have a much faster siever (based on iterating 2r-1 on the remainder rather than trial division) but I haven't tested it enough to be 100% confident in it.
Once I do some final testing on my new siever I'll be able to sieve to a higher n in the same time period and therefore remove more candidate k,n pairs.
I'm also approaching the point where mpz_probab_prime_p() takes almost as long as doing the proth test directly. Not sure what I'll do when it becomes too much of a burden.