Solving a Single Congruence Equation

[Thomas Klemm]

This program shouldn't result in an overflow:

Code:

#!/usr/bin/python

def add(a, b, n):
    result = a + b
    return result if result < n else (a - n) + b

def minus(a, b, n):
    result = a - b
    return result if 0 <= result else result + n

def double(a, n):
    return add(a, a, n)

def times(a, b, n):
    result = 0
    while a > 0:
        if a % 2:
            result = add(result, b, n)
        a /= 2
        b = double(b, n)
    return result

def inverse(a, n):
    p, q = n, a
    u, v = 0, 1
    while q > 0:
        r = p / q
        u, v = v, minus(u, times(r, v, n), n)
        p, q = q, p - r * q
    return u
    
a, b, n = 5, 3, 17
print times(inverse(a, n), b, n)
    
a, b, n = 999999999998, 1, 999999999999
print times(inverse(a, n), b, n)

Maybe somebody feels like translating that for the Prime?

Cheers
Thomas