pollard-strassen_factorization_method_no_polynomials.sf

#!/usr/bin/ruby

# Pollard-Strassen O(n^(1/4)) factorization algorithm.

# Without using polynomials.

# Illustrated by David Harvey in the following video:
#   https://yewtu.be/watch?v=_53s-0ZLxbQ

func pollard_strassen_factorization(n, d = min(500, 1+n.ilog2), tries = min(1000, 100*d)) {

    # In the original algorithm, d = ceil(n^(1/4))
    # d = 1+n.iroot(4)

    var a = random_prime(n)

    var baby_steps = @(1..d).map_reduce {|b|
        mulmod(b, a, n)
    }

    #var x = Poly(1)
    #var f = baby_steps.map {|k| (x-k) % n }.binsplit {|a,b| a * b }
    var b = powmod(a, d, n)

    for k in (2 .. tries) {

        #b = powmod(a, k*d, n)      # original operation
        b = powmod(b, k, n)         # p-1 smooth approach

        var t = baby_steps.map {|k| submod(b, k, n) }.reduce {|a,b|
            mulmod(a, b, n)
        }

        var g = gcd(t, n)

        if (g.is_between(2, n-1)) {
            return g
        }
    }

    return 1
}

say pollard_strassen_factorization(503*863)
say pollard_strassen_factorization(2**64 + 1)
say pollard_strassen_factorization(2.of { 1e7.random_prime }.prod)