Notices
Results 1 to 4 of 4

Thread: Modular Multiplicative Inverse (context of RSA)

  1. #1 Modular Multiplicative Inverse (context of RSA) 
    New Member
    Join Date
    Apr 2009
    Location
    Switzerland
    Posts
    2
    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.


    Reply With Quote  
     

  2.  
     

  3. #2 Re: Modular Multiplicative Inverse (context of RSA) 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote 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


    Reply With Quote  
     

  4. #3 Re: Modular Multiplicative Inverse (context of RSA) 
    New Member
    Join Date
    Apr 2009
    Location
    Switzerland
    Posts
    2
    Quote 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.
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

Bookmarks
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
  •