# Prime Identification easier than Prime Factorization?

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

-
It's easier to test for a number's compositeness than to actually factor said number. – J. M. Aug 8 '12 at 14:26
No, primality tests can be much faster: en.wikipedia.org/wiki/Primality_test – Qiaochu Yuan Aug 8 '12 at 14:28
After verifying that your number is not even, you can check for divisibility with only odd divisors... (i.e. j += 2). – J. M. Aug 8 '12 at 15:18
@J.M. be careful with what you say there, it simply is not known whether you can factor numbers fast. – sxd Aug 8 '12 at 15:43
@Dimitri, okay, append "with current techniques". – J. M. Aug 8 '12 at 16:01

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.

-
FWIW: I'm not fond of calling things like Miller-Rabin "primality tests" myself; if these tests say a number is composite, then it is definitely composite; but a number that passes these tests may or may not be prime (though exceptions have yet to be found). For guaranteeing primality, you need something like a primality certificate. – J. M. Aug 8 '12 at 15:07
I'm not sure it's necessarily practical to need 100% accuracy - running Miller-Rabin with ten bases, all of which will take relatively little time, will give an answer with probability of error about 1/12 the probability of dying from lightning strike. – K. Hu Aug 8 '12 at 17:46
I need 100% accuracy on the integers between 1 and 10^20. If there is a single false positive or negative in this range it is useless for my purposes. – Andrew Tomazos Aug 9 '12 at 4:03
Miller-Rabin on the first 12 primes as bases is definitely accurate up to $3 \times 10^{18}$ and conjectured to be accurate up to $3 \times 10^{23}$. If you find a counterexample you could get a short paper out of it. – Erick Wong Aug 9 '12 at 4:41
@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. – Charles Mar 7 '15 at 2:45

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.

-