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
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
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