Shop OBEX P1 Docs P2 Docs Learn Events
Another Modulus (Modulo math) question... — Parallax Forums

Another Modulus (Modulo math) question...

Don MDon M Posts: 1,652
edited 2014-03-11 17:40 in Propeller 1
I am looking at this equation:

e * d = 1(mod(p - 1) * (q - 1))

I need to solve for d. I know ahead of time that:

e = 7
p = 17
q = 11

So the equation now looks like this:

7 * d = 1(mod(17 - 1) * (11 - 1))

or

7 * d = 1(mod160)

According to the article I'm reading the answer is d = 23. I can't figure out how they get that and they don't tell you.

If I do 1(mod160) I get the answer of 1 so I want to try and solve it backwards as 1(mod160) / 7 = d but that doesn't work.

Can someone help me understand this ? I'd like to put it into a spin equation if possible.

Thanks.
Don

Comments

  • Duane DegnDuane Degn Posts: 10,588
    edited 2014-03-09 20:06
    Do you a link to the original article?

    When you write "1(mod160)" is that the same as Spin's:
    1//160

    ?

    For the equation:
    y := 1//x

    Won't y equal 1 for all legal values of x except when x equals 1?

    I feel like I'm missing something.
  • ElectrodudeElectrodude Posts: 1,658
    edited 2014-03-09 21:37
    Looks like you're trying to make RSA private keys. You want to use the Extended Euclidean Algorithm. I forget how exactly you use it but I want to go to bed now. If you or someone else hasn't figured it out by sometime tomorrow or the next day I'll help you if I have the time.

    electrodude
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2014-03-09 21:52
    7 * d = 1(mod160) is the same as saying (7 * d) // 160 == 1 in Spin.

    -Phil
  • Don MDon M Posts: 1,652
    edited 2014-03-10 03:01
    Duane Degn wrote: »
    Do you a link to the original article?

    Duane- Here's the link- http://blogs.msdn.com/b/plankytronixx/archive/2010/10/23/crypto-primer-understanding-encryption-public-private-key-signatures-and-certificates.aspx

    The equations in question are about 1/3 down the page.
  • Don MDon M Posts: 1,652
    edited 2014-03-10 03:03
    Phil Pilgrim (PhiPi) wrote: »
    7 * d = 1(mod160) is the same as saying (7 * d) // 160 == 1 in Spin.

    -Phil

    How do you solve for d ?
  • Don MDon M Posts: 1,652
    edited 2014-03-10 03:25
    Electrodude wrote: »
    Looks like you're trying to make RSA private keys. You want to use the Extended Euclidean Algorithm. I forget how exactly you use it but I want to go to bed now. If you or someone else hasn't figured it out by sometime tomorrow or the next day I'll help you if I have the time.

    electrodude

    You are correct. I'd appreciate any input you could provide. Trying to see if this is possible using the Propeller.
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2014-03-10 03:37
    Don M wrote:
    How do you solve for d ?

    What numbers == 1 mod 160? Well, let's see: 161, 321, 481, ... So
    7 * d = 161, or 7 * d = 321, or 7 * d = 481, or ...

    Pick one whose solution for d is an integer.

    -Phil
  • Don MDon M Posts: 1,652
    edited 2014-03-10 03:54
    Phil Pilgrim (PhiPi) wrote: »
    What numbers == 1 mod 160? Well, let's see: 161, 321, 481, ... So
    7 * d = 161, or 7 * d = 321, or 7 * d = 481, or ...

    Pick one whose solution for d is an integer.

    -Phil

    Phil- I don't understand your answer here. If you look back at the #1 post I mentioned that the article I was reading (posted in #5 above) says the answer is 23. So now using your format how do you get 23 as an answer to that equation? Sorry not trying to be silly here but I don't understand how it's done.
  • r.daneelr.daneel Posts: 96
    edited 2014-03-10 04:19
    Don M wrote: »
    Phil- I don't understand your answer here. If you look back at the #1 post I mentioned that the article I was reading (posted in #5 above) says the answer is 23. So now using your format how do you get 23 as an answer to that equation? Sorry not trying to be silly here but I don't understand how it's done.

    d * 7 = 161
    => d = 161 / 7
    => d = 23
  • Mark_TMark_T Posts: 1,981
    edited 2014-03-10 09:25
    You need to find the multiplicative inverse of e, which as been pointed out is done
    with a variant of Euclid's algorithm.
    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures
  • xanatosxanatos Posts: 1,120
    edited 2014-03-11 17:21
    160/7 = 22.8571... Round up = 23
    7 * 23 = 161
    161(mod 160) = 1

    or

    160+1=161
    161/7=23
    d=23

    modulo is just the remainder after a division... am I missing something about what was asked?

    d=23
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2014-03-11 17:34
    xanatos wrote:
    ... am I missing something about what was asked?
    No -- but maybe about what's already been answered. :)

    -Phil
  • xanatosxanatos Posts: 1,120
    edited 2014-03-11 17:40
    Phil Pilgrim (PhiPi) wrote: »
    No -- but maybe about what's already been answered. :)

    -Phil

    I swear I never saw r.daneel's answer... but, yes... indeed. :)
Sign In or Register to comment.