How to Compute Inverses in U_n

1. Run the first algorithm on the rational number g/n.

   			ai	rest
   81	/	187	0	81	/	187
   187	/	81	2	25	/	81
   81	/	25	3	6	/	25
   25	/	6	4	1	/	6
   6	/	1	6	0

2. If the expansion length is odd, make it even by converting the expansion to improper form, that is, by replacing the last coefficient “a” with “a−1,1”.

   [0,2,3,4,6]
   [0,2,3,4,5,1]

3. Run the second algorithm.

   		0	2	3	4	5	1
   0	1	0	1	3	13	68	81
   1	0	1	2	7	30	157	187

4. The answer is the next-to-last denominator, here 157.

Here's an alternate version that shows why the answer is the next-to-last denominator.

4. Turn the last two columns into a matrix in the usual way.

   81	68
   187	157

5. Because the expansion length is even, the matrix has determinant 1.

   81 × 157 − 68 × 187 = 1

6. When that equation is considered mod 187, the second term drops out.

   81 × 157 ≡ 1

For a bit more about determinants, see Approximation Quality, and for a bit more about improper forms, see Two Examples. You don't need to read the rest of that thread.

For some purposes, it's useful to stop with the equation in step 5. For example, that equation is a self-contained proof that the original two numbers really were relatively prime: any number that divides both divides the left-hand side, and therefore also the right-hand side, which is 1. Another small thing that continued fractions are good for!

I optimized the original version of the algorithm for clarity, not speed, so if speed is what you want, you should probably make a few adjustments. Here are the ones that come to mind.

• Don't calculate the numerators in step 3!
• If you know that g has been normalized into the range (0,n), you can skip the first iteration in step 1. On the other hand, if you don't know that g has been normalized, you can let the first iteration take care of that.
• Of course you can skip the last iteration in step 3.
• If you're writing code, the obvious approach is to make the continued fraction expansion a variable-length data structure, but that requires memory allocation. Here's a different approach that avoids that. If you interleave steps 1 and 3, you can fit everything into a fixed amount of memory, and if you unroll the loop to get two copies, you can reduce swapping and also keep track of whether the length is even or odd.

If you do nothing except interleave steps 1 and 3, the result is basically the extended Euclidean algorithm.

That all sounds complicated and fragile, though. Maybe the sweet spot is more toward the clarity side.

• Implement the first algorithm with an optional argument that requests either the proper form, the improper form, the even-length form, or the odd-length form.
• Implement the second algorithm as a pair of functions so that you can calculate the denominators separately.

  int[] calcNums  (int[] a) { return calcTerms(0,1,a); }
  int[] calcDenoms(int[] a) { return calcTerms(1,0,a); }

Before I learned about the algorithm above, I had to use other methods to compute inverses.

• In An Example I used table lookup, which is a bad idea on so many levels. Building a table requires a lot of time and space, so you don't want to do that unless you're going to be doing a lot of calculations with the same modulus n. If you wanted to do the same thing without a table, you'd need to find a generator, which isn't easy, and compute a discrete logarithm, which is hard. And that's if the group U_n is cyclic! In general, you'd need to factor n to determine the structure of the group, find a set of generators, and compute a multidimensional discrete logarithm as in the very last point of Multiplication in Base 10.
• At the end of The Next Block I presented a little algorithm I'd thought of. It's actually not bad! It just becomes inefficient for large numbers.

That's all, folks!