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
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
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