Scala, Fermat's little theorem

Today, another Scala posting by way of example, using the interesting Fermat's Little Theorem test for primality. This is a probabilistic test that provides no false negatives (if a number is found not prime, that is certain) but can provide false positives (a number indicated as prime is not certain to be so). The test can be run a number of times with a different base value (a) to gain increasing confidence that the number is prime.

Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

There are a small set of special numbers that "fool" this test, these are the Carmichael numbers. Further details can be found here http://en.wikipedia.org/wiki/Carmichael_number

Carmichael numbers are extremely rare. There are only 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601.

Because the Carmichael numbers are a special subset of the Fermat prime numbers that satisfy the same condition, they can be known as absolute Fermat pseudoprimes. The Fermat "primes" can be known as Fermat pseudoprimes. If we remove the absolute Fermat pseudoprimes from the Fermat Pseudoprimes then we end up with the absolute primes.

There are revised versions of this test that remove the false positive Carmichael numbers, such as the famous Miller-Rabin test (Miller 1976, Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n - 1)st power is congruent to 1 modulo n.

For this Scala example, I'm only using the original Fermat's Little Theorem. Here is the Scala file, the main contains a number of test cases.

import java.util.Random;

object FermatsLittleTheorem {

 def main(args : Array[String]) {

   val attempts = 10;  // the number of attempts, higher numbers give greater confidence in positive results.

   var n = 17;
   println("result1: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 13
   println("result2: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 11
   println("result3: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 9
   println("result4: n = " + n + ", res = " + fastPrime(n, attempts))  // should be false
 }

 def fastPrime(n : Int, times : Int) : Boolean = {

   if (times == 0)
     true
   else
     if (fermatTest(n)) fastPrime(n, times - 1) else false
 }

 def expmod(base : Int, exp : Int, m : Int) : Int = {

   if (exp == 0)
     1
   else if (even(exp))
     remainder(square(expmod(base, (exp / 2), m)), m)
   else
     remainder(base * expmod(base, exp - 1, m), m)
 }

 def square(n : Int) : Int = {

   n * n
 }

 def even(n : Int) : Boolean = {

   remainder(n, 2) == 0
 }

 def remainder(n : Int, d : Int) : Int = {

     n % d
 }

 def fermatTest(n : Int) : Boolean = {

   def tryIt(a : Int) : Boolean = {

     val res = expmod(a, n, n)
     println("res = " + res + ", a = " + a + ", n = " + n + ", a % n = " + a % n)
     res == a % n
   }

   tryIt(random(n - 1) + 1)    // get a random int between 1 and n
 }

 def random(n : Int) : Int = { // return a random value between 0 and n - 1

   val random = new Random();

   random.nextInt(n);
 }
}

This was refactored from the following Scheme code, as an exercise in Scala:

(define (expmod base exp m)
 (cond ((= exp 0) 1)
   ((even? exp)
    (remainder (square (expmod base (/ exp 2) m))
      m))
   (else
     (remainder (* base (expmod base (- exp 1) m))
      m))))

 (define (even? n)
   (= (remainder n 2) 0))

 (define (fermat-test n)
   (define (try-it a)
     (= (expmod a n n) a))
     (try-it (+ 1 (random (- n 1)))))

 (define (fast-prime? n times)
   (cond ((= times 0) true)
     ((fermat-test n) (fast-prime? n (- times 1)))
   (else false)))

A note of the tail recursiveness of the function fastPrime:

Comment (summary) from PaulP from #scala:

"It's not tail recursive but only for one reason. It's neither final nor private. It just needs to be able to determine it won't be overridden. It'd be tailrec if in an object.

There has also been discussion of a @tailrec annotation so you could get a compiler warning if a tagged function wasn't compiled tailrec as you'd thought."


.