fermat_factorization_method.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 22 December 2017
# https://github.com/trizen

# Simple implementation of Fermat's factorization method.

# See also:
#   https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

func fermat_factorization(n) {

    # Check for primes and negative numbers
    return []  if (n <= 1)
    return [n] if n.is_prime

    # Check for divisibility by 2
    if (n.is_even) {
        var v = n.valuation(2)
        return (v.of(2) + __FUNC__(n >> v))
    }

    var p = n.isqrt
    var q = (p*p - n)

    while (!q.is_square) {
        q += ((p++ << 1) + 1)
    }

    var s = q.isqrt

    var f1 = (p + s)
    var f2 = (p - s)

    __FUNC__(f1) +
    __FUNC__(f2) -> sort
}

for n in ([160587846247027, 5040, 65127835124, 6469693230]) {
    var factors = fermat_factorization(n)
    say "#{factors.join(' * ')} = #{n}"
    assert(factors.all { .is_prime })
    assert_eq(factors.prod, n)
}

__END__
12672269 * 12672383 = 160587846247027
2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 = 5040
2 * 2 * 11 * 19 * 6359 * 12251 = 65127835124
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230