proof modolu

by hope2009
Tags: modolu, proof
hope2009 is offline
Dec1-09, 08:54 PM
P: 3
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)

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

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
Phys.Org News Partner Science news on
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
farful is offline
Dec15-09, 04:10 PM
P: 56
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

Register to reply

Related Discussions
Proof of God and proof that he's vain General Discussion 25
Eigenvalue proof. (2nd opinion if my proof is right please) Calculus & Beyond Homework 3
Proof: Compare two integral(Please look at my surgested proof) Calculus & Beyond Homework 11
Proof: One more irrationality proof :) Introductory Physics Homework 5
A proof is a proof---says Canadian Prime Minister General Math 0