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.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.
a + a' = 0
b * b' = 1
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 modWhat 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)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,
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)
a*a' ≡ 1 (mod n)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.
aa' +n(-k) = 1
An inverse for a number a modulo n exists if and only if (iff) gcd(a,n) = 1Clearly 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 10We 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 AlgorithmNow, 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):
gcd(11,4):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:
11 = 4*2 + 3
4 = 3*1 + 1
3 = 1*3 + 0
Rearrange the second equation for 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".
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
Table method for finding inversesIn 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)Let's work through an example. Say we want to find the inverse of 615 mod 817. First we do the euclidean algorithm:
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.
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)
CodeAnd, 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 Loop '-----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 Wend findInverse = xTwo 'return! End Function