Scheme -- Test primality

Posted on 2006-05-27
Last Modified: 2010-04-17

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

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

    LVL 18

    Accepted Solution


    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.
    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 for a really deep analysis on the theme.


    Featured Post

    What Should I Do With This Threat Intelligence?

    Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

    Join & Write a Comment

    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…

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now