Euclidean algorithm, inverses and division in mod

This is the second bit of math necessary for the little cipher I implemented (First part about the euclidean algorithm here). Today we'll look at inverses in modular arithmetic.

In order to do arithmetic in any "system" or field, there must exist two identities. These identities are the additive identity and the multiplicative identity. In the fields/systems we are used to working in (Naturals, Integers, Reals and Complex, in addition to modulus systems) the additive identity is 0 and the multiplicative identity is 1.
We think of a' and b' as the inverses of a and b, respectively.
a + a' = 0

b * b' = 1
As you can see, when we add the inverse of a to a, we are really subtracting a from a. When we are multiplying the inverse of b with b, we are dividing b by itself. This way we do not need to define division and subtraction; they are simply the inverse operations of addition and multiplication.
Side note: Something interesting: the multiplicative inverse does not exist for the additive identity. For example, there is no possible value of a' to get 0*a' = 1

"Division" in mod

What we would call "division" in modular arithmetic is different from division in the other number systems we are familiar with. In a mod system, we cannot simply divide a number as we would in Integers, Reals, Naturals, etc. We cannot, for example, do the following:
This is wrong!

2x ≡ 8 mod 10
x ≡ (8/2) mod 10
x ≡ 4 mod 10

This is not the correct approach!

In order to "divide" eight by two to solve for x, we must instead multiply eight by the inverse of 2 in mod 11 arithmetic. The multiplicative inverse of a number a in modulus n is defined:
a * a' ≡ 1 (mod n)
The question now becomes, is there an algorithm for finding the inverse? And can we guarantee that an inverse will exist? We can certainly do it by trial and error or inspection for certain cases. In a pinch a spreadsheet will do, and I have certainly used that approach. But there is another way!

First, let us examine the situations where an inverse will exist and when it won't. We want to know in what situations the following congruence is solvable, as a general case:
ax ≡ b (mod n)
Which, by the division algorithm, can also be written as this (relevant later):
ax - b = kn
ax -kn = b
ax + n(-k) = b (this is a linear equation. If we solve for only integer solutions, it is called a Diophantine equation)
This Diophantine equation is solvable only when gcd(a,n) | b; that is when the gcd(a,n) evenly divides b. In our more specific example for finding the inverse,
a*a' ≡ 1 (mod n)
aa' +n(-k) = 1
Only under the condition that the gcd(a,n) | 1 . The only way this is possible is for the gcd(a,n) to be 1.
An inverse for a number a modulo n exists if and only if (iff) gcd(a,n) = 1
Clearly the first thing we must do is check the gcd. This is where primes come in handy; with a prime modulus the gcd will always equal 1 (as long as out a value is less than the prime. If it is a multiple of the prime than the gcd will equal the prime, the value will be congruent to 0 in modular arithmetic and the inverse will be undefined.). If your modulus is a prime number you don't even have to check; you can be assured that an inverse will exist. Going back to our original example, if we wanted to solve for x:
2x ≡ 8 mod 10
We can immediately see that no inverse exists because gcd(2, 10) does not equal 1. In fact, x can be both 4 and 9 to satisfy this equation, so it is not solvable for a single x.

Extended Euclidean Algorithm

Now, how do we find the inverse, knowing that one exists? The answer is in the Euclidean algorithm. Lets, for example, examine the Euclidean algorithm for finding the gcd(4, 11):

11 = 4*2 + 3
4 = 3*1 + 1
3 = 1*3 + 0
You may notice something interesting here. We can rearrange the set of equations to be expressed in terms of 11 and 4 and be equal to 1 by using back substitution. This is called the extended euclidean algorithm:
Rearrange the second equation for 1:

4 = 3*1 + 1
4 - 3*1 = 1
4 + 3*(-1) = 1

(Does the form of the above look familiar? It is aa' + n(-k) = 1!)
Rearrange the first equation (11 = 4*2 + 3) for 3:

11 = 4*2 + 3
3 = 11 - 4*2


4 + (11 - 4*2)*(-1) = 1
4 + 11*(-1) - 4*(-2) = 1
4 + 11*(-1) + 4*(2) = 1
4*(3) + 11*(-1) = 1
As by our equation aa' + n(-k) = 1, we can see that 3 is the inverse of 4 (and vice versa) modulus 11. This process can get tricky and tedious for long sets of equations, or even not-so-long sets. There is an easy shorthand though. It's called the "magic box" or the "table method".

Table method for finding inverses

In most incarnations, the magic box is also used to calculate the GCD too, but I prefer the method where you do the euclidean algorithm as normal and then pull the quotients from it (how our textbook presents it). It works like this:
1. Do the euclidean algorithm and find the gcd(a, modulus)
2. If the gcd is not 1, there is no inverse
3. Draw a table with the columns labeled with all the quotients in the order they were computed and two rows. The first row is labeled "1 0" and the second row is labeled "0 1" It should look like this:

4. For each cell in the table, calculate the value. The value for cell xi will be:
xi-2 - (xi-1 * qi)
Where you use the values from the row labels when i-1 and i-2 are negative. To visualize:

5. The results in the rightmost column once the table is done will be your inverses. The top one will be the inverse of the first dividend and the bottom one will be the inverse of the second dividend.
Let's work through an example. Say we want to find the inverse of 615 mod 817. First we do the euclidean algorithm:

We then construct our table using the quotients obtained:

And then we do the calculation:

This is easy enough to automate in any spreadsheet program.

Now, the first value (-137) is the inverse of 817 mod 615. The second value (182) is the inverse of 615 mod 817. We can check to verify:
615*182 = 111930 ≡ 1 (mod 817)
817 * (-137) ≡ 202 * 478 ≡ 96556 ≡ 1 (mod 615)


And, of course, I implemented it in code for my little cipher.
Here is the VBA code (again, because it is so similar to pseudocode!). It is a modified version of the euclidean algorithm function from previously. It first runs the euclidean algorithm and stores all the quotients in an array. (Because the number and value of the quotients matters, we have to make sure the parameters are in the correct order, a requirement not necessary with the previous euclidean algorithm function)
After doing that, it runs a loop to do one row (the second one, which is the relevant one) of the table method. After, it adjusts the result to be a positive value between zero and the modulus (for practicality) before returning it. Simple enough! It looks long because of comments and because I chose to be very explicit.

Function findInverse(m As Integer, modulus As Integer) As Variant
    Dim i As Integer
    Dim xOne As Integer
    Dim xTwo As Integer
    Dim temp As Integer
    Dim remainder As Integer
    Dim divisor As Integer
    Dim dividend As Integer
    Dim allQuotients() As Integer
    '-----Calculate the GCD and quotients
    'The expression a = b * q + r will become
    'dividand = divisor * q + remainder
    dividend = m
    divisor = modulus

    'need to swap for this one because the number of quotients matters;
    'if a < b then we get a large initial quotient as an extra step
    If modulus > m Then
        dividend = modulus
        divisor = m
    End If
    ReDim allQuotients(0 To (dividend - 1)) 'resize the array
    remainder = dividend 'arbitrary initialization
    i = 0

    '---Loop go get quotients
    Do While remainder > 1
        'calculate new q and r
        remainder = dividend Mod divisor
        allQuotients(i) = dividend \ divisor
        i = i + 1
        'Shift over b and r to replace a and b
        dividend = divisor
        divisor = remainder
    '-----If the GCD is not 1, then the inverse is not defined.
    If Not (remainder = 1) Then
        findInverse = "No Inverse"
        Exit Function
    End If
    ReDim Preserve allQuotients(0 To (i - 1)) 'cut off unused elements
    '-----Calculate the Inverse using the quotients obtained
    'Extended euclidian algorithm with block method
    'Uses only the second row.
    '    |(quotients q1, q2, ...)
    '0 1 | 0 - 1 * q1 | 1 - (0 - 1 * q1) * q2 |...
    xOne = 0
    xTwo = 1
    temp = 0 'arbitrary initialisation
    '---Loop for the calculation of the inverse via block
    For i = 0 To UBound(allQuotients)
        temp = xOne - (xTwo * allQuotients(i))
        xOne = xTwo
        xTwo = temp
    Next i
    '-----Make sure the inverse is between zero and the modulus
    While xTwo < 0
        xTwo = xTwo + modulus
    findInverse = xTwo 'return!
End Function

0 things about

Euclidean algorithm, inverses and division in mod

Post a Comment

Copyright 2012 Phile not Found. See About
Powered by Blogger

"Whenever you find that you are on the side of the majority, it is time to pause and reflect."