Post Reply 
Solving a Single Congruence Equation
04-16-2014, 07:48 AM
Post: #8
RE: Solving a Single Congruence Equation
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
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Solving a Single Congruence Equation - Thomas Klemm - 04-16-2014 07:48 AM



User(s) browsing this thread: 1 Guest(s)