complex_modular_multiplicative_inverse.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 19 December 2018
# https://github.com/trizen

# Algorithm for computing the modular multiplicative inverse of complex numbers:
#   1/a mod n, with |gcd(a, n)| = 1.

# Solution to `x` for:
#   a*x = 1 (mod n)

func complex_gcd(a, b) {

    while (b != 0) {

        var q = round(a/b)
        var r = (a - q*b)

        (a, b) = (b, r)
    }

    return a
}

func complex_modular_inverse (a, n) {

    var g = complex_gcd(a, n)

    g.abs == 1 || return NaN

    func inverse(a, n, i) {

        var (u, w) = (i, 0)
        var (q, r) = (0, 0)

        var c = n

        while (c != 0) {
            q = round(a/c)
            r = (a - q*c)

            (a, c) = (c, r)
            (u, w) = (w, u - q*w)
        }

        return u%n
    }

    [g.conj, 1, -1, 1i, -1i].lazy.map {|i| inverse(a, n, i) }.first_by {|t|
        (t * a) % n == 1
    }
}

say complex_modular_inverse(42, 2017)          #=> 1969
say complex_modular_inverse(3+4i, 2017)        #=> 1291+968i
say complex_modular_inverse(91+23i, 2017)      #=> 590+405i
say complex_modular_inverse(43+99i, 2017)      #=> 1709+1272i
say complex_modular_inverse(43+99i, 1234567)   #=> 1019551+667302i

# Non-existent inverses
say complex_modular_inverse(43+99i, 1234)      #=> NaN