Modular inverse calculation stuck

Question

Here is my code so far:

def mod_div(a, b, n): 

if gcd(b,n) != 1:
    return 'Undefined'    

for x in range(1, n):
        if b*x%n == a%n:      
            return x   

this code takes the function gcd() which I made and returns the gcd, which i then use to calculate the inverse. I did a search of the questions, and none of them seem to be giving me the correct answer.

My problem is this: when I do div_mod(3,2,7), the code returns 5, as it should. However, when I do it for large numbers, such as n > 10000, it takes very long for the solution to compute because of the iteration through n to find the correct number.

I tried looking at the other questions, and in their answers, they all have a similar thing, but instead of going for i in n, they all return x%n if gcd != 1. this does not help me,and it does not give the right answer.

For example. if I use a=12, b = 3 and n= 11 it should return 4,but all the functions I found except for mine all return 1.

I want to know if thereis a more efficient way to use eulids extended theorem other than testing each n, and hoping one works.

Answer 1

You are right that the Extended Euclidean Algorithm solves this task. However you don't need to call it n times - you only need it once. Check http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Here is an imperative python algorithm from http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

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

O(1) space and around O(log n) time in the worst case.

Now, to divide modulo n, we have by definition

def moddiv(a, b, n):
    binv = modinv(b, n)
    if not binv:
        return None
    return a * binv % n