Modular Inverse is an important topic in number theory. To understand modular inverse one has to know basics of modular arithmetic or congruence which in this post I will skip. one might find this helpful for the basic . we would discuss a bit(a tiny bit though :P ) advanced thing here.
sometimes we need to find (a/b)% mod . we can simplify this as follows:
(a/b)% mod = ( a% mod * b^-1 % mod) % mod
here b^-1 % mod = modular inverse of b
we can find this modular inverse by extended euclidean algorithm (or also by big mod algorithm using Euler's theorem if mod is prime).Anyway at first let's check how mathematically modular inverse is calculated:
suppose we want to find modular inverse of 27 mod 392.
dividend = divisor (quotient) + remainder
392 = 27*(14) + 14 ......................... (1)
27 = 14*(1) + 13 ..........................(2)
14 = 13*(1) + 1 ............................(3)
every time divisor is becoming dividend and remainder is becoming divisor except in the first step.
Now form the last equation, we would solve for remainders, just doing side changing,
1 = 14 + 13*(-1) ....................(4)
13 = 27 + 14*(-1) ....................(5)
14= 392 + 27*(-14) ....................(6)
we can backwardly substitute values of remainders in the previous equation (4).
1 = 14 + [27 + 14 * (-1)] * (-1) ................. // just replacing values of 13 from equation (5)
=>1= 14 + 27*(-1) + 14(1)
=> 1 = 14*(2) + 27 *(-1)
Now again we can replace the values of 14 from the equation (6) in the same procedure,
1 = [392 + 27*(-14)] * (2) + 27*(-1)
=>1 = 392*(2) + 27*(-28) + 27*(-1)
=>1 =392*(2) + 27*(-29) .................... (7)
we can recall we are calculating modular inverse of 27 mod 392,so if we mod equation (7) by 392
we get,
392%392=0 and -29 % 392= 363
replacing these values in (7)
1= 0 + 27*(363)
=> 27*(363)= 1 (mod 392)
so 27^-1 = 363 (mod 392)
Before advancing to code for calculating the modular inverse one must know the math behind it.
No comments:
Post a Comment