Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Procedure to compute a multiplicative inverse

  1. Mar 20, 2012 #1
    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 [itex]x[/itex] satisfying [itex]ax \equiv 1 \pmod m[/itex], where [itex]\gcd(a,m)=1[/itex].

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

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

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

    Using the same procedure repeatedly, we obtain a sequence of divisors [itex]q_1, q_2, ..., q_n[/itex] until [itex]r_n=1[/itex]; then the multiplicative inverse of [itex]a[/itex] is the product of all [itex]q_1, q_2, ..., q_n[/itex] (reduce it modulo [itex]m[/itex] 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: Mar 20, 2012
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted