sidef-scripts/Math/holf-pell_factorization.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 11 February 2019
# Edit: 19 February 2019
# https://github.com/trizen

# A simple integer factorization method, using square root convergents and small multipliers, inspired by William Hart's OLF method.

# Efficient in factoring numbers that are close to perfect squares.

# See also:
#   https://en.wikipedia.org/wiki/Pell%27s_equation
#   https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization
#   https://programmingpraxis.com/2014/01/28/harts-one-line-factoring-algorithm/

func create_pell (n, k) {

    var N = (n * k)
    var x = N.isqrt
    var y = x
    var z = 1
    var r = 2*x

    var (f1, f2) = (1, x)

    {
        y = (r*z - y)
        z = ((N - y*y) / z)
        r = ((x + y) // z)      #/ integer division /

        (f1, f2) = (f2, (r*f2 + f1)%n)

        (f1, z)
    }
}

func holf_pell_factorization(n, iter=10000) {

    var x = n.isqrt

    return n if n.is_prime
    return x if n.is_square

    var check_congruence = { |u,v|
        if (v.is_square) {
            var g = gcd(u - v.isqrt, n)
            if (g.is_between(2, n-1)) {
                return g
            }
        }
    }

    for k in (1 .. iter) {

        var f = create_pell(n, 2 * k)

        2.times {
            check_congruence(f())
        }
    }
}

say [763546828801, 6031047559681, 184597450297471, 732785991945841, 18641350656000001, 55212580317094201, 9969815738350374661, 73410179782535364796052059].map(holf_pell_factorization) #=> [2621431, 4122691, 60761401, 121060801, 409599991, 452852401, 35723051521, 34271896307617]

say holf_pell_factorization(501683471371554052574395593328002385856815909090992391730837714087618687789563199570570904748766683429134165931903849390638583070098709002977060135024453968329425015984667453956539152122050098453561508979991634026587581234275280113197333815352093406638207274145779974221097800552970426675930071039999999999999999999999999)
say holf_pell_factorization(126727335216251935155511386856292269344039435369339223952841818402341178946842787391524421251641584095380245040090295288781100410936392638772851127857739674291628104658325634644906472821071273024005952940961745631724673242565456694421601734604687078622903224894582381431189998689129881876425605119999999999999999999999999)

__END__
44796583413093193287215634651008016235543664766903178304924622669704447996750359492291902708555128777401775001997067403960568901240094719999999999999999999999999
90526428980625828101248261690578699475994489216450172824535174978361071993433018140673220056871822737666086983202407045503649654589358079999999999999999999999999