sidef-scripts/Math/holf_factorization.sf

#!/usr/bin/ruby

# Hart’s One-Line Factoring Algorithm.

# See also:
#   https://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf
#   https://programmingpraxis.com/2014/01/28/harts-one-line-factoring-algorithm/

func HOLF_factor(n, iter=100000) {

    for k in (1..iter) {

        var s = 1+isqrt(n * 4*k)
        var m = powmod(s, 2, n)

        if (m.is_square) {
            var g = gcd(n, s - m.isqrt)

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

    return 1
}

say HOLF_factor(126727335216251935155511386856292269344039435369339223952841818402341178946842787391524421251641584095380245040090295288781100410936392638772851127857739674291628104658325634644906472821071273024005952940961745631724673242565456694421601734604687078622903224894582381431189998689129881876425605119999999999999999999999999)
say HOLF_factor(501683471371554052574395593328002385856815909090992391730837714087618687789563199570570904748766683429134165931903849390638583070098709002977060135024453968329425015984667453956539152122050098453561508979991634026587581234275280113197333815352093406638207274145779974221097800552970426675930071039999999999999999999999999)

__END__
90526428980625828101248261690578699475994489216450172824535174978361071993433018140673220056871822737666086983202407045503649654589358079999999999999999999999999
44796583413093193287215634651008016235543664766903178304924622669704447996750359492291902708555128777401775001997067403960568901240094719999999999999999999999999