On 2014-03-12 04:56, Watson Ladd wrote:
A few hours? The trick is to sieve: the numbers for various N are in an arithmetic progression with a=2^64. As a result, you can determine which N are possible because of small prime obstructions, thus decreasing the amount of work to be done. In fact, I think your first N is entirely determined by considerations modulo the primes less than 100. Secondly look at (p-1)/2=q instead. If this is known prime determining if 2*q+1 is prime is quick using Pocklington's Theorem: you don't need to do the extensive primality testing.
Exactly, have you tried this? For the 8192 bit prime, you are to eliminate 4,743,158 candidates. Suppose:- you are using a double sieve on both primes that eliminates all but 0.6-0.7% of the candidates, - you are doing the Fermat test of the Pocklington criterion first, and this eliminates all but 1-2% of the remaining candidates,
then this means your search will still be dominated by some 300,000 modular exponentiations with a 8192 bit modulus and with 8191 bit exponents. Let's say a reasonably optimized implementation performs such an exponentiation in 400ms on a contemporary PC. This leaves you with an expected running time of 20 min.