carmichael_factorization_method.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 17 March 2019
# https://github.com/trizen

# A new factorization method for numbers with exactly three distinct prime factors of the form:
#
#   n = a * (a+x) * (a+y)
#   n = a * ((a±1)*x ± 1) * ((a±1)*y ± 1)
#
# for x,y relatively small.

# Many Carmichael numbers and Lucas pseudoprimes are of this form and can be factorized relatively fast by this method.

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

func solve_cubic_equation (a, b, c, d) {

    var p = (3*a*c - b*b)/(3*a*a)
    var q = (2*b**3 - 9*a*b*c + 27*a*a*d)/(27 * a**3)

    var t = (icbrt(-(q/2) + isqrt((q**2 / 4) + (p**3 / 27))) +
             icbrt(-(q/2) - isqrt((q**2 / 4) + (p**3 / 27))))

    var x = round(t - b/(3*a))

    return x
}

func carmichael_factorization(n, l=2, h=23) {

    var try_parameters = {|a,b,c|

        var t = solve_cubic_equation(a, b, c, -n)
        var g = gcd(t, n)

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

    # It's also possible to iterate over `z in (1..3)` and set `y = y/z`
    @(l..h).combinations(2, {|x,y|

        var a = x*y
        var b = (2*a - x - y)
        var c = (a - x - y + 1)

        try_parameters(a, b, c)
        try_parameters(a, -b, c)
        try_parameters(1, x+y, a)
        try_parameters(a, y-x, -c)

        try_parameters(a, ( 2*y + 1)*x + y, (y + 1)*x + (y + 1))
        try_parameters(a, (-2*y - 1)*x - y, (y + 1)*x + (y + 1))
    })

    return 1
}

say carmichael_factorization(7520940423059310542039581)                                         #=> 79443853
say carmichael_factorization(1000000032900000272110000405099)                                   #=> 10000000103
say carmichael_factorization(570115866940668362539466801338334994649)                           #=> 4563211789627
say carmichael_factorization(8325544586081174440728309072452661246289)                          #=> 11153738721817
say carmichael_factorization(1169586052690021349455126348204184925097724507)                    #=> 166585508879747
say carmichael_factorization(61881629277526932459093227009982733523969186747)                   #=> 1233150073853267
say carmichael_factorization(173315617708997561998574166143524347111328490824959334367069087)   #=> 173823271649325368927