CODEWITHSUNDEEP
algorithmmathprimes
tskuzzy
tskuzzy

Reputation: 36476

Simple deterministic primality testing for small numbers

I am aware that there are a number of primality testing algorithms used in practice (Sieve of Eratosthenes, Fermat's test, Miller-Rabin, AKS, etc). However, they are either slow (e.g. sieve), probabalistic (Fermat and Miller-Rabin), or relatively difficult to implement (AKS).

What is the best deterministic solution to determine whether or not a number is prime?

Note that I am primarily (pun intended) interested in testing against numbers on the order of 32 (and maybe 64) bits. So a robust solution (applicable to larger numbers) is not necessary.

Upvotes: 5

Views: 1842

Answers (4)

user448810
user448810

Reputation: 17866

If you can factor n-1 it is easy to prove that n is prime, using a method developed by Edouard Lucas in the 19th century. You can read about the algorithm at Wikipedia, or look at my implementation of the algorithm at my blog. There are variants of the algorithm that require only a partial factorization.

If the factorization of n-1 is difficult, the best method is the elliptic curve primality proving algorithm, but that requires more math, and more code, than you may be willing to write. That would be much faster than AKS, in any case.

Are you sure that you need an absolute proof of primality? The Baillie-Wagstaff algorithm is faster than any deterministic primality prover, and there are no known counter-examples.

If you know that n will never exceed 2^64 then strong pseudo-prime tests using the first twelve primes as bases are sufficient to prove n prime. For 32-bit integers, strong pseudo-prime tests to the three bases 2, 7 and 61 are sufficient to prove primality.

Upvotes: 2

rossum
rossum

Reputation: 15693

  1. Use the Sieve of Eratosthenes to pre-calculate as many primes as you have space for. You can fit in a lot at one bit per number and halve the space by only sieving odd numbers (treating 2 as a special case).

  2. For numbers from Sieve.MAX_NUM up to the square of Sieve.MAX_NUM you can use trial division because you already have the required primes listed. Judicious use of Miller-Rabin on larger unfactored residues can speed up the process a lot.

  3. For numbers larger than that I would use one of the probabilistic tests, Miller-Rabin is good and if repeated a few times can give results that are less likely to be wrong than a hardware failure in the computer you are running.

Upvotes: 1

Mysticial
Mysticial

Reputation: 471359

Up to ~2^30 you could brute force with trial-division.

Up to 3.4*10^14, Rabin-Miller with the first 7 primes has been proven to be deterministic.

Above that, you're on your own. There's no known sub-cubic deterministic algorithm.

EDIT : I remembered this, but I didn't find the reference until now:

http://reference.wolfram.com/legacy/v5_2/book/section-A.9.4

PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.

As of 1997, this procedure is known to be correct only for n < 10^16, and it is conceivable that for larger n it could claim a composite number to be prime.

So if you implement Rabin-Miller and Lucas, you're good up to 10^16.

Upvotes: 11

Alexey Frunze
Alexey Frunze

Reputation: 62086

If I didn't care about space, I would try precomputing all the primes below 2^32 (~4e9/ln(4e9)*4 bytes, which is less than 1GB), store them in the memory and use a binary search. You can also play with memory mapping of the file containing these precomputed primes (pros: faster program start, cons: will be slow until all the needed data is actually in the memory).

Upvotes: 3

Related Questions