Register to reply

Proof modolu

by hope2009
Tags: modolu, proof
Share this thread:
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
Wildfires and other burns play bigger role in climate change, professor finds
SR Labs research to expose BadUSB next week in Vegas
New study advances 'DNA revolution,' tells butterflies' evolutionary history
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