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

  • 2
    It's easier to test for a number's compositeness than to actually factor said number.2012-08-08
  • 3
    No, primality tests can be much faster: http://en.wikipedia.org/wiki/Primality_test2012-08-08
  • 0
    After verifying that your number is not even, you can check for divisibility with only **odd** divisors... (i.e. `j += 2`).2012-08-08
  • 1
    @J.M. be careful with what you say there, it simply is not known whether you can factor numbers fast.2012-08-08
  • 0
    @Dimitri, okay, append "with current techniques".2012-08-08

2 Answers 2