Inconsistent result of a pow() with a negative exponent

[CookiePLMonster]

Calculating a private RSA key via pow(x, -1, phi) appears to fail in Brython.

Minimal reproducible example:

p = 800275543
q = 33679599593
e = 65537
n = p*q
d = pow(e, -1, (p-1) * (q-1))
print(f'd: {d}, n: {n}')

CPython 3.11.3: d: 21203499539617337777, n: 26952959852310653999

Brython 3.11.3 (Brython 3.12.3 yields the same results, however): d: -5749460278213441087, n: 26952959852310653999

CPython's calculation results match WolframAlpha: https://www.wolframalpha.com/input?i=PowerMod%2865537%2C+-1%2C+%28800275543-1%29*%2833679599593-1%29%29

[CookiePLMonster]

To make testing easier, egcd could be used to verify validity of results:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

p = 800275543
q = 33679599593
e = 65537
phi = (p-1) * (q-1)

assert pow(e, -1, phi) == modinv(e, phi)

[coproc]

The value -5749460278213441087 for d is not really wrong, it is just another representative of the same residuum class modulo phi = (p-1)*(q-1) = 26952959817830778864: d - phi = 21203499539617337777 - 26952959817830778864 = -5749460278213441087

So in the 3-argument version of pow probably only a line like this is missing at the end: if result < 0: result += mod

[PierreQuentel]

Thanks for the report @CookiePLMonster. @coproc you were right, the solution was to make sure that the modulo is positive.