modular_multiplicative_inverse.sf

#!/usr/bin/ruby

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

# Algorithm presented in the book:
#
#   Modern Computer Arithmetic
#           - by Richard P. Brent and Paul Zimmermann
#

func modular_inverse (a, n) {

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

    var c = n

    while (c != 0) {
        (q, r) = divmod(a, c)
        (a, c) = (c, r)
        (u, w) = (w, u - q*w)
    }

    u += n if (u < 0)

    return u
}

say modular_inverse(42, 2017)   #=> 1969