I need an algorithm to decide quickly in the worst case if a 20 digit integer is prime or composite.
I do not need the factors.
Is the fastest way still a prime factorization algorithm? Or is there a faster way given the above relaxation?
In any case which algorithm gives the best worst case performance for a 20 digit prime?
Update:
Here is the simple method I started with:
int64 x = 981168724994134051LL; // prime int64 sq = int64(ceil(sqrt(x))); for(int64 j = 2; j <= sq; j++) { if (x % j == 0) cout << "fail" << endl; }
It takes 9 seconds on my 3.8Ghz i7 3930K. I need to get it down by a factor of about 1000. Going to try a low end "primorial" sieve and see what that does.
Update 2:
I created a prime sieve using $2.3.5.7.11.13.17 = 510510 = c$ entries. And then searched for factors in blocks of 510510, disregarding factors that are divisible by one of the 7 mentioned primes by a lookup table. It actually made running time worst (11 seconds), I suspect because the memory access time is not worth it compared to the density of numbers cooprime to $(2,3,5,..,17)$