I need to test primality on intervals between numbers which are really big (in the range of long long), so i need some fast algorithm for checking if a number is prime or not. Please suggest your ideas.
+1
A:
I came up with a really good algorithm, that is much faster than checking all the divisors - which of course also lets me crack public key encryption.
Hang on - I just need to close the window, there are all these black helicopters overhead ........
(Or look at http://stackoverflow.com/questions/627463/how-can-i-test-for-primality)
Martin Beckett
2010-04-06 16:46:58
Factorizing composite numbers (which would be needed to crack RSA) is different from just testing if a number is prime (which doesn't necessarily require to find any specific factors). In fact implementing RSA requires to find primes with hundreds of digits, which would be unfeasible with a simple "check all potential divisors" algorithm.
sth
2010-04-06 16:57:05
Yes but if there were a faster method of testing primes, you wouldn't be telling anybody about it here ;-) The question was goign to get closed as dupe anyway.
Martin Beckett
2010-04-06 17:36:18
+7
A:
One good method is the Miller-Rabin test. It should be noted however, that this is only a probabilistic test.
cobbal
2010-04-06 16:47:24
Miller-Rabin can be adapted to be deterministic under the assumption of the Generalized Riemann Hypothesis. Since the GRH is widely believed to true I could envision a scenario where you were using this test as though it were proven deterministic since it is by far the fastest.
Mark Lavin
2010-04-07 18:12:38
A:
Fastest would probably be to look it up in a precomputed list of primes. See here for example, they have up to 2^43112609-1 (largest known prime).
JRL
2010-04-06 16:49:02
This would not work. No computer has ever had enough storage to hold a list this long. The list would require more than a billion gigabytes of storage without compression, based on a rough estimate for `pi(2^64)`.
Dietrich Epp
2010-04-06 16:58:12
+6
A:
I believe that the asymptotically fastest current (non-probabilistic) primality test is the "Lenstra/Pomerance improved AKS", which has complexity that is essentially O(n^6).
However, the range of long long (assuming a typical system where that is a 64 bit integer) is not really that big. In particular, there are only ~200 million primes less than 2^32, so using a fast probabilistic test, followed by trial division with a precomputed list of primes (or just looking the number up in a list of primes, if you have one) would be pretty darn fast in that range, and is probably the right way to go about it.
Stephen Canon
2010-04-06 16:53:45
You don't need to do trial division after the probabilistic test. If you run the probabilist test n iterations then the probability of an incorrect answer is 1/2^n so if n = 100 the algorithm would be incorrect 1 in 10^30 times. It is better to just run the probabilistic test more iterations than doing trial division.
theycallhimtom
2010-04-06 18:23:29
+2
A:
I would suggest the GNU MP library that uses the Miller-Rabin algorithm. I have used it for a few months and it's very fast.
Specifically, the function mpz_probab_prime_p does this, you can also use another function mpz_nextprime to find the next prime number greater than a number. I can post code samples if you would like.
grokus
2010-04-06 16:55:59
+1
A:
Cobbal and grokus are right. The Miller-Rabin test is the most useful of the available algorithms. Yes, it is probabilistic, but really shouldn't scare you off. The test is the most widely used for practical purposes.
Note that the probability of false positives (there are no false negatives) can be made arbitrarily small by repeating the test.
Rob Lachlan
2010-04-06 17:00:19
+1
A:
Take a look at my answer here:
how to test a prime number 1000 digits long?
The test is very fast. If you are working in the 64-bit or smaller range, you can throw in a GCD with 30030 to save a bit of time for the majority of numbers.
280Z28
2010-04-06 17:03:01
A:
If you want to test a long long for primality then the Baillie PSW primality test is a good choice. This test does one strong pseudoprime test and one Lucas test and hence is very fast. It is expected that there exist some composites that pass this test, but so far none are known, and there certainly is no exception below 1015. A variant of this test is for example used in Mathematica.
Accipitridae
2010-04-06 21:14:14