How Do You Find the Modular Multiplicative Inverse?

[scouter]

Hi all,

i would like to tell me, how to find the modular multiplicative inverse (MMI), of a mod n...


Untill now, my thought was that we can find the MMI, with the extended euclidean algorithm, by calculating
gcd (a,n)...
As an output, we will take 3 numbers (d,x,y)... and i have been told that x is the MMI that i am looking for...
For example, if i am looking the MMI of 36mod5, with the extended euclidean algorithm, we will take at the output (1,1,-7) and 1 is the answer..

But as i am trying to do, some examples, my results are not the same, as the book ones...
So what is the solution?

 

[HallsofIvy]

You dont' say what results you got or what the books says so I don't see how anyone can help here. Can you give an example from the book where your answer and the book's answer are different? And, of course, give both answers.

(Using the Euclidean algorithm to find the multiplicative inverse of 36 mod 6 seems like overkill. 36= 1 (mod 5) and of course the multiplicative inverse of 1 is 1!)

 

[scouter]

Well, the algorithm i am talking about is, from the book
Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
amd the exact algorithm is:

INPUT: a ε Z[SUB]n[/SUB].
OUTPUT: a[SUP]−1[/SUP] mod n, provided that it exists.
1. Use the extendedEuclidean algorithm to find integers x and y such
that ax + ny = d, where d = gcd(a, n).
2. If d > 1, then a[SUP]−1[/SUP] mod n does not exist. Otherwise, return(x).

I found an example, from a greek book, which want us to calculate, the modular multiplicative inverse, of 45modulo4.. the results that is given is 45.. my result is 1.. if the algorithm above is correct, then maybe my problem is with the extended euclidean algorithm, so i will write you exactly how i found 1...

 

[mathwonk]

mod 4, 45 =1, so the inverse is also 1, with no great effort.

 

[scouter]

mod 4, 45 =1, so the inverse is also 1, with no great effort.

So the problem is with the euclidean algorithm.. not with the mod multiplicative inverse algorithm... :\

 

[HallsofIvy]

I asked before what result you got using the Euclidean algorithm and you still have not answered. I suspect that the problem is NOT with the Euclidean algorithm but with your mis-use of it.

The multiplicative inverse of 45, mod 4, is the number, n such that 45n= 1 (mod 4) which is the same as saying 45n= 1+ 4m for some integer m. That is the same as 45n- 4m= 1. 4 divides into 45 11 times with remainder 1: 45- 11(4)= 1 so one solution to 45n- 4m= 1 is n= 1, m= 11.
The Euclidean algorithm gives n= 1 just as it should.

 

[TONY G]

i think i can answer or give an answer to that question u guys are eatin ur mouths on.

 

[scouter]

Well, i found the solution... i couldn't undestand the chinese theorem, so i missused the result x...
you were right HallsofIvy.. thanksSsSs