MBE_factorization_method.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 12 March 2022
# Edit: 15 March 2022
# https://github.com/trizen

# A new integer factorization method, using the binary exponentiation algorithm with modular exponentiation.

# We call it the "Modular Binary Exponentiation" (MBE) factorization method.

# Similar in flavor to the Pollard's p-1 method.

func f(a,b,n) {

    var c = 1

    b.bits.flip.each {|x|
        c = powmod(a, c, n) if x
        a = powmod(a, a, n)
    }

    return c
}

func MBE_factor(n, max_k = 10000) {

    say "[*] Factoring #{n}"

    for k in (1..max_k) {

        #var a = idiv(n, k)
        var a = irand(2,n)         # randomised version
        var c = 1

        a.bits.flip.each {|x|
            c = powmod(a, c, n) if x
            a = powmod(a, a, n)
        }

        # Equivalently:
        # c = f(a, a, n)

        var g = gcd(c-1, n)

        if (g.is_between(2, n-1)) {
            say "[*] Found factor #{g} with k=#{k} -- took O(n^(1/#{n.log(1+k).round(-4)}))"
            return g
        }
    }

    return 1
}

for n in (1..5) {
    var n = 2.of { 1e7.random_prime }.prod
    MBE_factor(n)
    say ''
}

__END__
[*] Factoring 3034271543203
[*] Found factor 604727 with k=177 -- took O(n^(1/5.5526))

[*] Factoring 43120971427631
[*] Found factor 5501281 with k=2 -- took O(n^(1/45.2935))