Fermat Primality Tester

FermatPrimalityTester.scala

import scala.util.Random
import scala.collection.immutable._
import scala.math._

class FermatPrimalityTester(rounds: Int) {
  private val this.rounds = rounds
  private val random = new Random

  def isPrime(subject: Int): Boolean = {
    return this.getRandomIntegers(subject)
      .forall(randomInt => this.modExp(randomInt, subject - 1, subject) == 1)
  }

  private def getRandomIntegers(subject: Int): Iterable[Int] = {
    return 0.until(this.rounds)
      .map(index => this.random.nextInt(subject - 1) + 1)
  }

  private def modExp(base: Long, exponent: Long, modulus: Long): Long = {
    if (exponent == 0)
      return 1

    val z = this.modExp(base, exponent / 2, modulus)

    if (exponent % 2 == 0)
      return (z * z) % modulus

    return base * (z * z) % modulus
  }
}