# Thread: Modular Multiplicative Inverse (context of RSA)

1. So I'm writing an essay about RSA encryption, and there is one step that I'm currently having some trouble with:
Determine d (using modular arithmetic) which satisfies the congruence relation : where d is the only unknown
It says that this is done with the extended Euclidean algorithm and with the modular multiplicative inverse. Here is a link to how this is done, and I understand it all until it all until the last step, where it says "a and m given, x the inverse, and q an integer multiple that will be discarded". What I don't understand is how this gives you the d value (in the initial equation). Also from what I gather, you would take the inverse of a ("x the inverse"?) and you discard q, however this doesn't give me a correct answer... Can anyone help me with this?
Also another question regarding modulo; if you have a large number such as 193284719827 mod (19), is there any way to find out what the value of it is other than subtracting multiples of 19 from the initial value?
Thanks
-Chris
By the way, sorry if this is in the wrong forum, I just figured that since it was the math of the encryption that I need help with and not the encryption itself that this is where it would go.  2. ### Related Discussions:

3. Originally Posted by Scorzerci
So I'm writing an essay about RSA encryption, and there is one step that I'm currently having some trouble with:
Determine d (using modular arithmetic) which satisfies the congruence relation : where d is the only unknown
It says that this is done with the extended Euclidean algorithm and with the modular multiplicative inverse. Here is a link to how this is done, and I understand it all until it all until the last step, where it says "a and m given, x the inverse, and q an integer multiple that will be discarded". What I don't understand is how this gives you the d value (in the initial equation). Also from what I gather, you would take the inverse of a ("x the inverse"?) and you discard q, however this doesn't give me a correct answer... Can anyone help me with this?
Also another question regarding modulo; if you have a large number such as 193284719827 mod (19), is there any way to find out what the value of it is other than subtracting multiples of 19 from the initial value?
Thanks
-Chris
By the way, sorry if this is in the wrong forum, I just figured that since it was the math of the encryption that I need help with and not the encryption itself that this is where it would go.
d

Your question is a bit unclear to me. But maybe this will help.

1. d is invertible mod n if and only if d and n are relatively prime.

2. To find the typical representative for m mod n your divide m by n and then the remainder is the representative.

193284719827 (mod 19) =17

How? 193284719827/19 = 10172879990.9

193284719827 - 10172879990x19 = 193284719827 - 193284719810 = 17  4. Originally Posted by DrRocket
d

Your question is a bit unclear to me. But maybe this will help.

1. d is invertible mod n if and only if d and n are relatively prime.
Ok maybe if I did this in an example:  This is the point where I don't really know where to go anymore.
If I follow the Extended Euclidean algorithm this is what I should do:  The final statement on the Wikipedia explanation on this says ""a and m given, x the inverse, and q an integer multiple that will be discarded""
(a=17, m=60, x=d, q=q)
From what I understand from that statement I should just discard "q", but I don't understand what I should be doing with the "d" value.

2. To find the typical representative for m mod n your divide m by n and then the remainder is the representative.

193284719827 (mod 19) =17

How? 193284719827/19 = 10172879990.9

193284719827 - 10172879990x19 = 193284719827 - 193284719810 = 17
Ok that makes sense, thanks.  5. Well, first you have to find a d and a q that satisfy that equation, then you can discard q since you have the d you're looking for.  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement