reset password
Author Message
layla08
Posts: 70
Posted 11:21 Nov 23, 2016 |

Hi classmates,

2 questions regarding multiplicative inverses:

1) What theorem/formula  can you use to get the M.I. of 14^-1 mod 238?

  • 238 is not prime, so we can't use a^p-2 mod p.
  • We can only use a^(totient(n) -1) mod n if GCD(a,n) = 1 and GCD(14, 238) = 14, so we can't use this either.

2) For lecture 9 (Blind Signature), slide 36, where you sign the partially blind signature, it says that the signer computes:

     t =h(a)d (σ(x2+1) β-2)2d mod n

       = 1577 (111*(172+1)*108-2)2*77 mod 119

       = 36*(111*290*542) 2*77 mod 119

       = 100

My question is how do you get from 108^-2 to 54^2? It might be something completely obvious, but I can't figure it out!

Thanks!

anuradharajakumar
Posts: 2
Posted 13:36 Nov 23, 2016 |

1. You can find multiplicative inverse only if gcd(a,n)=1. You can check this in the Review 1 ppt - slide 45. In your case since gcd(14, 238) is not 1, 14 doesnt have a multiplicative inverse.

2. For 108^-2, find β-1 mod n =54 and then( β-1)2 = 54^2

layla08
Posts: 70
Posted 08:34 Nov 24, 2016 |

Thank you so much :) Extremely helpful!