sidef-scripts/Math/gaussian_factors.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 09 May 2022
# https://github.com/trizen

# Find the factors of a Gaussian integer.

# See also:
#   https://www.alpertron.com.ar/GAUSSIAN.HTM
#   https://en.wikipedia.org/wiki/Table_of_Gaussian_integer_factorizations

func gaussian_factors(Gauss z) {

    var Z = z
    var n = z.norm
    var factors = []

    for p,e in (n.factor_exp) {
        if (p == 2) {
            var t = Gauss(1,1)
            while (z % t == 0) {
                factors << t
                z /= t
            }
        }
        elsif (p % 4 == 3) {
            var t = Gauss(p)
            while (z % t == 0) {
                factors << t
                z /= t
            }
        }
        else {
            for a,b in (sum_of_squares(p)) {

                var t1 = Gauss(a,b)
                var t2 = Gauss(b,a)

                while (z % t1 == 0) {
                    factors << t1
                    z /= t1
                }

                while (z % t2 == 0) {
                    factors << t2
                    z /= t2
                }
            }
        }
    }

    if (z != Gauss(1,0)) {
        factors << z
    }

    assert_eq(factors.prod.abs, Z.abs)
    assert_eq(factors.prod.norm, n)

    return factors.sort.run_length
}

var z = Gauss(440, -55)
var factors  = gaussian_factors(z)

say factors                             #=> [[Gauss(-1, 0), 1], [Gauss(1, 2), 1], [Gauss(2, 1), 2], [Gauss(2, 3), 1], [Gauss(11, 0), 1]]
say factors.prod_2d {|p,e| p**e }       #=> Gauss(440, -55)