Modulo operation difference between Swift and Python

Question

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

Perhaps you should mention which big integer library you are using in Swift, `BInt` is not a standard library type. — Martin R, Dec 31 '16 at 00:07
Quick experiment: what is `-2%5` in Swift? -2 or 3? If it is -2, this probably explains the discrepancy (though exactly how isn't obvious). — John Coleman, Dec 31 '16 at 00:17
`-2 % 5 = -2` in Swift: http://stackoverflow.com/questions/41180292/negative-number-modulo-in-swift, but I don't know how that big integer library computes it. — Martin R, Dec 31 '16 at 00:21
That means that Swift (like many programming languages) isn't quite using the standard mathematical definition of modulus (which always returns a non-negative remainder). But -- Python has -2%5 = 3. Since you are testing with negative numbers, it isn't surprising that you get different results. -- Good point about how that big integer library computes, though presumably it would be consistent. — John Coleman, Dec 31 '16 at 00:24
Actually `%` is called the *remainder operator* in Swift, not modulus. — Martin R, Dec 31 '16 at 00:25
According to PARI/GP, the modular inverse of `-34499628904269660561674201530767158034393542375844615658184142552908072257357` for modulus `115792089237316195423570985008687907853269984665640564039457584007908834671663` is `37732016455592228448156445462498416408852156224504820822700452822953572406827`, and that is printed neither by Swift or Python code. — Martin R, Dec 31 '16 at 00:27
Seems right here, or is there a reason THIS would not be correct? https://www.wolframalpha.com/input/?i=Mod%5B-34499628904269660561674201530767158034393542375844615658184142552908072257357,+115792089237316195423570985008687907853269984665640564039457584007908834671663%5D — , Dec 31 '16 at 00:35
@BrettDoffing: The modular inverse in WolframAlpha is `PowerMod[-34499628904269660561674201530767158034393542375844615658184142552908072257357, -1, 115792089237316195423570985008687907853269984665640564039457584007908834671663]` and that returns `37732016455592228448156445462498416408852156224504820822700452822953572406827` as well. — Martin R, Dec 31 '16 at 00:41
Sorry, yes, the return value is indeed 37732016455592228448156445462498416408852156224504820822700452822953572406827 — , Dec 31 '16 at 00:56
The outputs I have shown are the first few iterations of the calculation. — , Dec 31 '16 at 00:58
What is crazy is that for my posted example the result is the same, however, with other calculations, the result is not, and I this is simply where I found the original differentiations between results. — , Dec 31 '16 at 01:00
Modular inverses are only unique mod p. It is conceivable that sometimes the Swift one returns `y-p` where `y` is the result returned by Python. I don't have a Swift compiler but your Python example reliably returns results which agree with my own implementation of modular inverses (and agrees with Wolfram Alpha). Note that the intermediate results for `x` and `p` in the Python case are all positive after the first iteration but the Swift keeps alternating signs with this input. Does the Swift output pass simple testing? — John Coleman, Dec 31 '16 at 01:10
I added `if p < 0 {p += x}` after `x = temp` in the swift implementation, and viola, it comes out the same as the python one. Whether this accounts for the remainder vs. modulo difference I couldn't say, but I will do some more test cases, and it seems, if we haven't solved the problem completely, that we're on the right track — , Dec 31 '16 at 01:31
Well, I can say the added statement solved all of my problems, and I am now able to generate a Bitcoin public key from a private key, so I have to thank you two for working me through this. — , Dec 31 '16 at 01:43

Modulo operation difference between Swift and Python

0 Answers0