Chinese remainder Theorem The Chinese remainder theorem provides a way of solving an equation mod n,where n=p*q and p and q are prime, solving equations mod p and mod q Consider b=g l mod p and b2=p-l mod q Ifa=a,b q+a,b2p we have that a=a,b,q+a b2p=a, mod p a1b1qtayb2p=a2 mod q So if i know a and b i know aChinese Remainder Theorem • The Chinese remainder theorem provides a way of solving an equation mod n, where n=p*q and p and q are prime, solving equations mod p and mod q – Consider b1 = q-1 mod p and b2 = p-1 mod q – If a = a1b1q+a2b2p we have that • a = a1b1q+a2b2p = a1 mod p • a = a1b1q+a2b2p = a2 mod q – So if I know a1 and b1 I know a