Extended Euclidean Algorithm

eea.swift

struct Row: CustomStringConvertible {
    var a: Int
    var b: Int
    var t1: Int
    var t2: Int
    var s1: Int
    var s2: Int
    
    var r: Int {
        return self.a % self.b
    }
    var q: Int {
        return self.a / self.b
    }
    var t: Int {
        return self.t1 - q * self.t2
    }
    var s: Int {
        return self.s1 - q * self.s2
    }
    
    var description: String {
        return "\(self.q)\t\(self.a)\t\(self.b)\t\(self.r)\t\(self.t1)\t\(self.t2)\t\(self.t)\t\(self.s1)\t\(self.s2)\t\(self.s)"
    }
}

public func extendedEuclidAlgo(x: Int, modulo: Int, printRows: Bool = false) -> (s: Int, t: Int, gcd: Int, inverse: Int?) {
    var lastRow = Row(a: modulo, b: x, t1: 0, t2: 1, s1: 1, s2: 0)
    var rows = [lastRow]
    while lastRow.r != 0 {
        if printRows {
            print(lastRow)
        }
        rows.append(lastRow)
        lastRow = Row(a: lastRow.b, b: lastRow.r, t1: lastRow.t2, t2: lastRow.t, s1: lastRow.s2, s2: lastRow.s)
    }
    if printRows {
        print(lastRow)
    }
    var inverse: Int? = nil
    if lastRow.b == 1 {
        inverse = lastRow.t2
        while inverse! < 0 {
            inverse! += modulo
        }
    }
    return (
        s: lastRow.s2,
        t: lastRow.t2,
        gcd: lastRow.b,
        inverse: inverse
    )
}