While addition, subtraction and multiplication are "compatible with the congruence relation" introduced by modular arithmetic, the same doesn't happen with division. This means that solving a simple equation such as a·x = 1 (mod m) is anything but trivial. In fact, determining x = a

^{-1}(mod m) that fulfills that equation is the whole object of this post...

There is, as always, the brute force approach, which I always like to visit first, so that I can later congratulate myself on how much the efficiency has improved with my deep insight. In this particular case, brute force means trying every number between 1 and m-1, and see if the m-modulo of its product with a is 1. :

def modInv1(a,m) :

"""Computes the modular multiplicative inverse of a modulo m,

using brute force

"""

a %= m

for x in range(1,m) :

if a*x%m == 1 :

return x

return None

Do notice that the possibility of no multiplicative inverse existing is contemplated in the code. This will actually be the case if a and m have any common factors, i.e. if they are not coprime. So the previous code could serve as a moron's approach to determining if two numbers are relatively prime. Not that I recommend it, though, as it should be clear that the code I have just produced will be very inefficient for large values of m.

The Extended Euclidean Algorithm

As stated, we are after a number x that fulfills a·x = 1 (mod m). This can of course be written as well as a·x = 1 + m·y, which rearranges neatly into a·x - m·y = 1. Since x and y need not be positive, we can write it as well in the standard form, a·x + m·y = 1. If a and m are coprime, this is a particular instance of a·x + b·y = gcd(a,b), where gcd(a,b) is the greatest common divisor of a and b. This equatiin is known as Bézout's identity, and can be efficiently solved using the extended Euclidean algorithm. To find a solution to our particular equation, this algorithm would proceed as follows:

- Rewrite the equation as a
_{n}·x_{n}+ m_{n}·y_{n}= 1, starting with n = 0 - Compute the quotient, q
_{n}, and the remainder, r_{n}, of a_{n}divided by m_{n}, and rewrite the original equation as (m_{n}·q_{n}+ r_{n})·x_{n}+ m_{n}·y_{n}=1 - Rearrange the terms in the equation to get m
_{n}·(q_{n}·x_{n}+y_{n}) + r_{n}·x_{n}= 1 - Do the changes of variables
- x
_{n+1}= q_{n}·x_{n}+y_{n}, - y
_{n+1}= x_{n}, - a
_{n+1}= m_{n,}and - m
_{n+1}= r_{n}

- x
- Repeat the process, until a
_{n}= 1, and m_{n}= 0. - Such equations has the trivial solution x
_{n}= 1, y_{n}= 0. - Work your way back to x
_{0}and y_{0}, noting that- x
_{n-1}= y_{n}, - y
_{n-1}= x_{n}- q_{n-1}·y_{n}

- x
- x
_{0}is the number we are after.

_{n}= 1 and m

_{n}= 0. It is in fact not always the case, as if a and m are not coprime, then the values we will arrive at are m

_{n}= 0, but a

_{n}= gcd(a,m). As a matter of fact, the gcd is normally computed using the Euclidean algorithm, dropping the adjective extended, which basically does the same as above, but without the back-tracking of the x

_{n}'s and the y

_{n}'s. With all of this in mind, we can write two functions, one calling the other, as follows:

def extEuclideanAlg(a, b) :

"""Computes a solution to a x + b y = gcd(a,b), as well as gcd(a,b)

"""

if b == 0 :

return 1,0,a

else :

x, y, gcd = extEuclideanAlg(b, a % b)

return y, x - y * (a // b),gcd

def modInvEuclid(a,m) :

"""Computes the modular multiplicative inverse of a modulo m,

using the extended Euclidean algorithm

"""

x,y,gcd = extEuclideanAlg(a,m)

if gcd == 1 :

return x % m

else :

return None

The gains in speed are tremendous with this new approach. Again, write your own testing function as an exercise, but mine spits out the following results...

>>> testModInv(1234,5,10000)

Got 4 using method 1 in 0.0160000324249 sec.

Got 4 using Euclidean algorithm in 0.0309998989105 sec.

>>> testModInv(1234,56789,10000)

Got 31800 using method 1 in 59.4000101089 sec.

Got 31800 using Euclidean algorithm in 0.047000169754 sec.

So while brute force is good enough, or even the best choice, for very small values of m, as soon as it grows, the benefits of the more elaborate algorithm are all too obvious. According to wikipedia, the algorithm we have coded has complexity O(log(m)

^{2}), i.e. time required to compute the modular multiplicative inverse is proportional to log(m)

^{2}.

can you give me the output of your calls to testModInv?

ReplyDelete