modular_fibonacci_number_cassini.sf

#!/usr/bin/ruby

# An efficient algorithm for computing Fibonacci(n) (mod m) for arbitrary large integers.

# Algorithm from:
#   https://metacpan.org/source/KRYDE/Math-NumSeq-72/lib/Math/NumSeq/Fibonacci.pm

# See also:
#   https://en.wikipedia.org/wiki/Fibonacci_number

func fibmod(n, m) {

    var (f, g, a) = (0, 1, -2)

    for k in (n.ilog2 ^.. 0) {

        g = (g*g)%m
        f = (f*f)%m

        var t = (g<<2 - f + a)

        f += g

        if (n.getbit(k)) {
            (f, g, a) = (t-f, t, -2)
        }
        else {
            (g, a) = (t-f, 2)
        }
    }

    return (g % m)
}

func fibonacci_factorization(n, B=10000) {

    var k = consecutive_lcm(B)      # lcm(1..B)
    var F = fibmod(k, n)            # Fibonacci(k) (mod n)

    return gcd(F, n)
}

say fibonacci_factorization(257221 * 470783,              700);     #=> 470783           (p+1 is  700-smooth)
say fibonacci_factorization(333732865481 * 1632480277613, 3000);    #=> 333732865481     (p-1 is 3000-smooth)