-1

I am working on an algorithm that calculates the multiplicative inverse of a number. I had to make a function to do this. However, I am stuck on an optimization.

My algorithm works, but only for relatively small numbers.

Given 3 numbers (a,b,n), i need to return a/b (mod n).

This part I can do. However, when n is really large, my code becomes impossibly slow because I am solving it this way:

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

My problem with this is again the size of n. If it gets huge, the code does not run.

Now, assuming my numbers are 3,2,7, I need to obtain the answer 5 without checking all the numbers. So I tried using the extended Euclidean algorithm.

This is what I did:

ax + by = 1
ax = 1 (mod n) => ax - 1 = qn, where q is an integer

I end up with the equation:

ax - qn = 1

If I sum in my numbers, I end up with:

3x + 7q = 1

How can I solve this? Is there a better way?

senshin
  • 10,022
  • 7
  • 46
  • 59
Lord Raikan
  • 21
  • 3
  • What are the approximate values of `n` (and also `a` and `b`) that you're working with that cause your original method to fail? – senshin Jan 16 '14 at 23:59
  • When you asked this question yesterday I told you to look up the extended Euclidean algorithm. You obviously failed to do so. In the search box at the top of the page, enter the phrase "extended Euclidean algorithm". You will find several relevant answers. Including mine. Perhaps you should give every solution on all those pages an upvote, as a way of thanking them for their work. I'm voting to close this question. Come back and ask a specific question if you have trouble implementing one of the solutions you find. – user448810 Jan 17 '14 at 00:56
  • @user448810 I did indeed look up the euclidian algorithm, which is what prompted me to ask this question. I am new to the site,so I did not think of searching for it here, but rather used external sources. – Lord Raikan Jan 17 '14 at 04:38

1 Answers1

1

What you are trying to solve is a diophantine equation

ax+by=1

where all numbers are integers. To solve something like this you need (as your title suggests) the extended euclidean algorithm which is explained best using a table. First you do the normal euclidean algorithm:

a b q
3 7 0
7 3 2
3 1 3
1 0

Where the new a is calculated by a-b*q and q is the quotient of a/b. Then you start at the bottom and go upwards to calculate x and y by starting with x=1 y=0. In each step the new x is the old y and the new y is xold-q*yold. To demonstrate this (unfortunately I could not format it better):

a b q  x  y
3 7 0
7 3 2
3 1 3
1 0    1  0

a b q  x  y
3 7 0 -2  0 // 1-0*(-2)
7 3 2  1 -2 // 0-2*1
3 1 3  0  1 // 1-3*0
1 0    1  0

3*(-2)+7*1=1
3*(-2)=1 (mod 7) | +7
-2=5 (mod 7)

So when you to fill the table or your own implemention you have the answer in the x field even though it might be negative in such a case you have to add N one time.

henje
  • 400
  • 2
  • 15