proof modolu


by hope2009
Tags: modolu, proof
hope2009
hope2009 is offline
#1
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)
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
Phys.Org News Partner Science news on Phys.org
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
farful is offline
#2
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