flt_factorization_method.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 02 August 2020
# https://github.com/trizen

# A new factorization method, inspired by Fermat's Little Theorem (FLT), for numbers that have prime factors close to each other.

# The idea is to try to find a non-trivial factor of `n` by checking:
#     gcd(f(n) - f(k), n)
# for several small k >= 1, where f(n) is a C-finite sequence.

# In this method, we use f(n) = b^n, for some fixed base `b`.

func FLT_factor(n, base = 2, tries = 1e4) {

    var z = powmod(base, n, n)
    var w = base
    var u = base*base

    if (z == base) {    # can't factor Fermat pseudoprimes
        return 1
    }

    tries.times {

        var g = gcd(z - w, n)

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

        w.mulmod!(u, n)
    }

    return 1
}

var p = 1e20.random_prime
var n = (p * p.next_prime * p.next_prime.next_prime)

say "Factoring: #{n}"
say ("Factor found: ", FLT_factor(n))

say ''

say FLT_factor(2**64 + 1, 3)                                                      #=> 274177
say FLT_factor(1169586052690021349455126348204184925097724507)                    #=> 166585508879747
say FLT_factor(61881629277526932459093227009982733523969186747)                   #=> 1233150073853267
say FLT_factor(173315617708997561998574166143524347111328490824959334367069087)   #=> 173823271649325368927
say FLT_factor(random_prime(1e30) * (2**128 + 1))                                 #=> 340282366920938463463374607431768211457