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.

Hi

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

-Mike

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

-Mike

1 Solution

Maybe you can make some use of the following pages:

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

Regards

Friedrich

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!!

}

else

{

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:

MODULAR_EXPONENTIATION(a, b, n)

{

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.

MILLER-RABIN(n, s)

{

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

}

WITNESS(a, n)

{

let (n-1) = u*2^t // t>=1 and u is odd

x_0 = MODULAR_EXPONENTIATION(a, u, n)

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.

Jose

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

Join Now
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.