I am trying to port a modular inverse operation from Python to Swift, and my modulo operation is producing different results. I am wondering if someone can point out why I am getting different results? I am using this as my BInt Library.
PYTHON CODE:
def inverse(x, p):
"""
Calculate the modular inverse of x ( mod p )
the modular inverse is a number such that:
(inverse(x, p) * x) % p == 1
you could think of this as: 1/x
"""
inv1 = 1
inv2 = 0
print "first x = %d" % x
print "first p = %d" % p
while p != 1 and p!=0:
inv1, inv2 = inv2, inv1 - inv2 * (x / p)
print "inv1 = %d" % inv1
print "inv2 = %d" % inv2
x, p = p, x % p
print "x = %d" % x
print "p = %d" % p
return inv2
SWIFT CODE:
func inverse(b: BInt, n: BInt) -> BInt {
var inv1 = BInt(1)
var inv2 = BInt(0)
var p = n
var x = b
print("first x = \(x)")
print("first p = \(p)")
while p != 1 && p != 0 {
var temp = inv2
inv2 = inv1 - inv2 * (x/p)
inv1 = temp
print("inv1 = \(inv1)")
print("inv2 = \(inv2)")
temp = p
p = x % p
x = temp
print("x = \(x)")
print("p = \(p)")
}
return inv2
}
Python results:
first x = -34499628904269660561674201530767158034393542375844615658184142552908072257357
first p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
inv1 = 0
inv2 = 1
x = 115792089237316195423570985008687907853269984665640564039457584007908834671663
p = 81292460333046534861896783477920749818876442289795948381273441455000762414306
inv1 = 1
inv2 = -1
x = 81292460333046534861896783477920749818876442289795948381273441455000762414306
p = 34499628904269660561674201530767158034393542375844615658184142552908072257357
inv1 = -1
inv2 = 3
x = 34499628904269660561674201530767158034393542375844615658184142552908072257357
p = 12293202524507213738548380416386433750089357538106717064905156349184617899592
Swift results:
first x = -34499628904269660561674201530767158034393542375844615658184142552908072257357
first p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
inv1 = 0
inv2 = 1
x = 115792089237316195423570985008687907853269984665640564039457584007908834671663
p = -34499628904269660561674201530767158034393542375844615658184142552908072257357
inv1 = 1
inv2 = 3
x = -34499628904269660561674201530767158034393542375844615658184142552908072257357
p = 12293202524507213738548380416386433750089357538106717064905156349184617899592
inv1 = 3
inv2 = 7
x = 12293202524507213738548380416386433750089357538106717064905156349184617899592
p = -9913223855255233084577440697994290534214827299631181528373829854538836458173