sidef-scripts/Math/sophie_germain_factorization_method_fast.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 11 November 2023
# https://github.com/trizen

# A simple factorization method, based on Sophie Germain's identity:
#   x^4 + 4y^4 = (x^2 + 2xy + 2y^2) * (x^2 - 2xy + 2y^2)

# This method is also effective for numbers of the form: n^4 + 4^(2k+1).

# See also:
#   https://oeis.org/A227855 -- Numbers of the form x^4 + 4*y^4.
#   https://www.quora.com/What-is-Sophie-Germains-Identity

func sophie_germain_decomposition(n) {

    var t = n.iroot(4)
    var u = (n - t**4)>>2

    if (u.is_power(4)) {
        var (x,y) = (t, u.iroot(4))
        assert_eq(n, x**4 + 4*y**4)
        return [x, y]
    }

    var t = (4*n).iroot(4)>>1
    var u = (n - 4*t**4)

    if (u.is_power(4)) {
        var (x,y) = (u.iroot(4), t)
        assert_eq(n, x**4 + 4*y**4)
        return [x, y]
    }

    return []
}

func sophie_germain_factors(n) {
    var arr = sophie_germain_decomposition(n) || return []
    var (x,y) = arr...
    var f = [x**2 - 2*x*y + 2*y**2, x**2 + 2*x*y + 2*y**2]
    assert_eq(f.prod, n)
    return f
}

var x = 642393874177414576297153561759
var y = 714067453700987

for n in ([(x**4 + 4*y**4), (4*x**4 + y**4)]) {
    say sophie_germain_decomposition(n)
}

assert_eq(sophie_germain_decomposition(x**4 + 4*y**4), [x, y])
assert_eq(sophie_germain_decomposition(y**4 + 4*x**4), [y, x])

say sophie_germain_factors(77001290479960160497341160397504245)
say sophie_germain_factors(19250322619990040124335290452638485)
say sophie_germain_factors(27606985387162255149739023449108101809804435888681546220650096903087665)
say sophie_germain_factors(173291855882550928723650886508942731464777317210988535948154973788413831737851601439998400381508723631086950685087723242628644864)
say sophie_germain_factors(13093562431584567480052758787310396608866568184172259157933165472384535185618698219533080369303616628603546736510240284036869026183541572213318079483505)

__END__
[642393874177414576297153561759, 714067453700987]
[714067453700987, 642393874177414576297153561759]
[277491095817736105, 277491031750210669]
[138745604154213509, 138745459629795665]
[166153499473114514665395754616490745, 166153499473114453560556010453601017]
[13164036458569648337239753460497746266300898132282617629258080512, 13164036458569648337239753460419861813422875717854660184319779072]
[3618502788666131106986593281521497141767405545090156208559806116590740633113, 3618502788666131106986593281521497099061968496512379043906292883903830095385]