Skip to content

Instantly share code, notes, and snippets.

@donn
Created October 20, 2023 12:16
Show Gist options
  • Save donn/5ef1ff04048ea81ad3a1b0b2b5dc5b91 to your computer and use it in GitHub Desktop.
Save donn/5ef1ff04048ea81ad3a1b0b2b5dc5b91 to your computer and use it in GitHub Desktop.
Extended Euclidean Algorithm
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
)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment