4
$\begingroup$

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)$

  • 0
    @Dimitri, okay, append "with current techniques".2012-08-08

2 Answers 2

1

There are several fast methods for determining primality, depending on whether you want a deterministic algorithm that always answers correctly or a probabilistic algorithm that always answers correctly if a number is composite but may answer that the number is prime when in fact it isn't. Fortunately, you can perform the tests so that each one reduces the probability of getting a false positive, so by running the algorithm several times you can get the probability that a number reported as prime actually is to be as close to one as you need. Qiaochu's link in the comments is a pretty good introduction to the subject; I usually use the Miller-Rabin test when explaining this to my students, since it's easy to understand and fast in practice.

  • 1
    @ErickWong: It follows from Jan Feitsma's 2009 calculations that M-R on the first 12 primes is accurate up to $2^{64}\approx1.8\cdot10^{19}.$ Not quite 10^20, though.2015-03-07
1

Seven iterations of Miller-Rabin test using a specific set of bases are guaranteed work flawlessly up to (at least) $2^{64}$. Also the Baillie-PSW test works up to $2^{64}$ with certainty (and we actually don't know any counter-example even beyond that bound).

Both tests need to calculate modular exponentiation with 64-bit arguments, which means their naive implementation would require $(2\times 64)$ bits for intermediate results. While some CPUs can perform this kind of calculation natively, the C compiler usually doesn't provide this possibility to the coder and one needs to implement their own arithmetic. But if you use GCC on 64-bit architecture and don't care about portability you can use __int128 data type.

On the positive side, even a very simple implementation of the 7-times-Rabin-Miller test yielded up speedup factor of roughly 20 000 over the trial division.