Solved

# Scheme -- Test primality

Posted on 2006-05-27
237 Views
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
0
Question by:nerdmike

LVL 5

Expert Comment

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.
0

LVL 24

Expert Comment

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:

Regards
Friedrich
0

LVL 18

Accepted Solution

Hi,

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
0

## Featured Post

### Suggested Solutions

I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

#### Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!