• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 296
  • Last Modified:

Scheme -- Test primality


I'm looking for a way to test if an arbitrary integer is prime quickly using available Scheme libraries.

note, trial division is not "quick enough" for me, and I will settle for a reasonably accurate probablistic algorithm

1 Solution
I'm no mathematician, and I don't know of any probabilistic way to do it, but one option would be to build up a look up table of known primes. If you know the range the number to be tested lies in, that's an advantage. If you know the numbers to be tested will be in a fairly narrow range, all you have to do is store that range, and you can do a quick lookup to verify you numer is a prime or not. It's probably not that big a deal to bundle a couple of megabytes of prime numbers with your app to allow quick lookups, or perhaps to spawn a background process to calculate the list your application requires.

Another option is to keep a fairly small lookup file, and when checking numbers all you have to do is divide by all the numbers in your list. For example, if you store the primes from 2 to 1000, you will know that you can be sure that your test is reliable for any number up to 1000 * 1000 or one million. When you get above this figure, you'll still catch a lot of primes, but the accuracy will go down the further above the square of your top number you get. Increasing the number of primes in your table will increase the accuracy and range, but will also increase the number of divisions required.

I know this isn't the answer you're looking for, but I hope it helps.
There are some rule floataing around for finding candidates for prime numbers, but there's no way to figure out without calculating, lostcarparks are therefor quite helpful

Maybe you can make some use of the following pages:

Jose ParrotGraphics ExpertCommented:

Sequence dividing has O(|number|)time complexity, that is a naive algorithm
Anyway, the number of tests depends on the number to test, that is T(n) = f(n). So, the bigger the number, the longer to test it. What matters is to keep the growth ratio as low as possible.

As you are looking for a probabilist approach, the first test would be:
PSEUDOPRIME(n) // n is the number to test for primality
   if MODULAR_EXPONENTIATION(2, n-1, n) not equivalent to 1 (mod n)
      return "NOT PRIME" // for sure!!
     return "PRIME"        // I hope!

There are only 22 values of n<10,000 for which this algorithm return an error, so it has a reasonable rightness. Not so bad.

The called function is:
   c = 0
   d = 1
   // let (b_(k), b_(k-1), ..., b(0) be the binary representation of b
   for (i=k; i>=0; i--)
      c = 2 * c
      d = (d * d) mod n
      if (b == 1)
         c = c + 1
         d = (d * a) mod n
   return d
If a, b and n are B-bit numbers, then thera are B arithmetic operations in the above function, and the total number of bit operations is O(n^3), say, O(n*n*n).

A more "precise" approach is the MILLER-RABIN and WITNESS algorithms.
   for (j=1; j<=s; j++)
      a = RANDOM(1, n-1)
      if WITNESS(a, n)
         then return "NOT PRIME"   // for sure!!
   return "PRIME"   // almost surely

   let (n-1) = u*2^t // t>=1 and u is odd
   for (i=1; i<=t; i++)
      x_(i) = (x_(i-1) ^2) mod n
      if (x_(i) == 1) and (x_(i-1) != 1) and (x_(i-1) != n-1)
         then return TRUE
   if (x_(t) != 1)
      then return TRUE
   return FALSE

The above pseudocodes don't care about returning from inside a loop, but a programming code must pay attention on it.

The complete and deep explanation on that is in a number of books. If you have access to a university library, take a look at Cormen, T. et al "Introduction to Algorithms".
You can also access http://en.wikipedia.org/wiki/Prime_number#Primality_tests for a really deep analysis on the theme.


Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now