Procedure to compute a multiplicative inverse

  • Context: Graduate 
  • Thread starter Thread starter dodo
  • Start date Start date
  • Tags Tags
    Inverse Procedure
Click For Summary
SUMMARY

The discussion presents a novel procedure for computing the multiplicative inverse of a number under a prime modulus, distinct from the extended Euclidean algorithm. The method involves a modified division algorithm to derive integers that lead to the multiplicative inverse through repeated iterations. The example provided demonstrates finding the inverse of 1234567 modulo 3257269, resulting in 1127070. The approach emphasizes modular arithmetic to manage large numbers effectively.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with the concept of multiplicative inverses
  • Knowledge of the division algorithm
  • Basic grasp of the Chinese remainder theorem
NEXT STEPS
  • Study the properties of prime numbers in modular arithmetic
  • Learn about the extended Euclidean algorithm for comparison
  • Explore modular exponentiation techniques
  • Investigate applications of the Chinese remainder theorem in cryptography
USEFUL FOR

Mathematicians, computer scientists, cryptographers, and anyone interested in number theory and modular arithmetic applications.

dodo
Messages
695
Reaction score
2
I think I found a procedure (other than the extended Euclidean algorithm) to compute the multiplicative inverse of a number; possibly a simpler method. It goes like this:

***EDIT: Ah, dang. I made a mistake. It will only work for a prime modulus.

Suppose we need to find x satisfying ax \equiv 1 \pmod m, where \gcd(a,m)=1.

We need to use a twisted version of the division algorithm, one that gives us integers q_1, r_1 such that m = q_1 a - r_1 (note the minus sign), with r_1 as small as possible. (So q_1=\lfloor m/a \rfloor+1.) Hence, q_1 a \equiv r_1 \pmod m.

Now, if r_1=1 we would be done: q_1 would be the multiplicative inverse we are looking for. So suppose it is not yet. But... if we had the multiplicative inverse of r_1, then we could multiply it to q_1 to get our solution.

So... rinse and repeat: find the inverse of r_1 (a smaller number, now). Note that \gcd(r_1,m)=1[/size] (<-- only guaranteed when m is prime!), so that the procedure can in fact be repeated.

Using the same procedure repeatedly, we obtain a sequence of divisors q_1, q_2, ..., q_n until r_n=1; then the multiplicative inverse of a is the product of all q_1, q_2, ..., q_n (reduce it modulo m if you wish).

Here is a worked example. Suppose you want the inverse of 1234567 modulo 3257269. We proceed as follows:
3257269 = 3 . 1234567 - 446432
3257269 = 8 . 446432 - 314187
3257269 = 11 . 314187 - 198788
3257269 = 17 . 198788 - 122127
3257269 = 27 . 122127 - 40160
3257269 = 82 . 40160 - 35851
3257269 = 91 . 35851 - 5172
3257269 = 630 . 5172 - 1091
3257269 = 2986 . 1091 - 457
3257269 = 7128 . 457 - 227
3257269 = 14350 . 227 - 181
3257269 = 17996 . 181 - 7
3257269 = 465325 . 7 - 6
3257269 = 542879 . 6 - 5
3257269 = 651454 . 5 - 1

The end was agonizing, but here we are: the inverse is 3 . 8 . 11 . 17 . 27 . 82 . 91 . 630 . 2986 . 7128 . 14350 . 17996 . 465325 . 542879 . 651454... or 1127070 (mod 3257269).

On a computer, the product could be accumulated modularly, so there is really no need to handle too large numbers.
 
Last edited:
Physics news on Phys.org
One can always break down large numbers via the modulo function and recombine the results with the Chinese remainder theorem. This is not new.