kotlin--fermats-factorization-method.kt

import java.math.BigInteger

fun main() {
    val factors = semiprimeFactors(BigInteger("769817083110377"))
    println("Factors: $factors") // Factors: (13685611, 56250107)
}

/**
 * Fermat's factorization method: https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
 * Semiprime n = a^2 - b^2 = (a - b) * (a + b)
 * Note: This form does not work for perfect primes, but would be trivial to add support for it.
 */
fun semiprimeFactors(n: BigInteger): Pair<BigInteger, BigInteger>? {
    var a = n.sqrt()
    val nHalf = n / BigInteger.TWO + BigInteger.ONE
    // This could be `while (true)` if input is guaranteed to be a semiprime
    while (a <= nHalf) { // Once halfway+1 is reached, then `(a-b)*(a+b)` lowest values will be `2*n` and `1*(n+1)`
        a++
        val b2 = a * a - n
        if (b2.isSquare()) {
            val b = b2.sqrt()
            return Pair(a - b, a + b)
        }
    }
    return null
}

fun BigInteger.isSquare() = this.sqrtAndRemainder()[1] == BigInteger.ZERO