modular_fibonacci_number_fast.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 19 June 2018
# https://github.com/trizen

# An efficient algorithm for computing the nth-Fibonacci number (mod m).

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

func fibmod(n, m) {

    var (f, g) = (0, 1)
    var (a, b) = (0, 1)

    for k in (0 .. n.ilog2) {
        (f, g) = ((f*a + g*b)%m, (f*b + g*(a+b))%m) if n.getbit(k)
        (a, b) = ((a*a + b*b)%m, (a*b + b*(a+b))%m)
    }

    return f
}

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)