elliptic-curve_factorization_method.sf

#!/usr/bin/ruby

# The elliptic-curve factorization method (ECM), due to Hendrik Lenstra.

# Algorithm presented in the YouTube video:
#   https://www.youtube.com/watch?v=2JlpeQWtGH8

# See also:
#   https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

func ecm(N, arange=100, plimit=10000) {

    return N            if N.is_prime
    return N.prime_root if N.is_prime_power

    var primes = plimit.primes

    for a in range(-arange, arange) {

        var x = 0
        var y = 1

        primes.each {|B|
            var t = B**plimit.ilog(B)

            var (xn, yn)
            var (sx, sy) = (x, y)

            var first = true

            while (t > 0) {

                if (t.is_odd) {
                    if (first) {
                        (xn, yn) = (sx, sy)
                        first = false
                    }
                    else {
                        var u = invmod(sx-xn, N)

                        if (!u) {
                            var d = gcd(sx-xn, N)
                            break if (d == N)
                            return d
                        }

                        var L  = (u*(sy-yn) % N)
                        var xs = ((L*L - xn - sx) % N)

                        yn = ((L*(xn - xs) - yn) % N)
                        xn = xs
                    }
                }

                var u = invmod(2*sy, N)

                if (!u) {
                    var d = gcd(2*sy, N)
                    break if (d == N)
                    return d
                }

                var L  = (u*(3*sx*sx + a) % N)
                var x2 = ((L*L - 2*sx) % N)

                sy = ((L*(sx - x2) - sy) % N)
                sx = x2

                sy || return N
                t >>= 1
            }
            (x, y) = (xn, yn)
        }
    }

    return N
}

say ecm(14304849576137459)
#say ecm(2**128 + 1)         # takes ~11 seconds