Full Example — Fermat’s factorization method

Fermat’s factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares. See more in Wikipedia.

#!/bin/sh
exec scala "$0" "$@"
!#

def decomposeInPrimes(t: Int): Set[Int] = {
  var factors = Set[Int]()

  def isqrt(number: Float): Int = {
    val squareroot:Int = Math.sqrt(number).toInt
    squareroot
  }

  def fermat(n: Int) {
    var number = n
    while(number % 2 == 0) {
      number /= 2
      factors += 2
    }
    if (number == 1) {
      return
    }
    var r = isqrt(number)
    var is_prime = true
    while (r < (number + 1) / 2) {
      val m = ((r * r) -  number).toFloat
      if (m >= 0 && Math.sqrt(m) == Math.floor(Math.sqrt(m))) {
        val s = isqrt(m)
        fermat(r - s)
        fermat(r + s)
        is_prime = false
        return
      }
      r += 1
    }
    if (is_prime == true) {
      factors += number
    }
  }
  fermat(t)
  factors
}

val test = args(0).toInt
println(decomposeInPrimes(test))

</p>

To run this program as script, save as “fermat.sh” and execute:

./fermat.sh 9941

</p>