Proof modolu

  1. Dec 1, 2009 #1
    In RSA: d_K (y)=y^d mod n and n=pq. Define

    d_p=d mod(p-1)

    d_q=d mod(q-1)
    Let

    M_p=q^(-1) mod p
    M_q=p^(-1) mod q
    And

    x_p=y^(d_p ) mod p
    x_q=y^(d_q ) mod q
    x=M_p qx_p+M_q px_q mod n

    Show that y^d=x mod n
    any help would be appraciated, thanks
     
  2. jcsd
  3. Dec 15, 2009 #2
    homework eh?

    use fermat's thm to prove y^d = y^(d_p) mod p (same for q)
    show x = x_p mod p (same for q)
    then use CRT to solve for x
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Proof modolu
  1. A proof (Replies: 1)

  2. Proof needed (Replies: 1)

  3. Help with a proof. (Replies: 5)

  4. Inverse Proof! (Replies: 2)

Loading...