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=q l mod p and b,=p-l mod q If a= a 101qta2b2p we have that a=a,b,q+a2b2p=a, mod p a=a,b,q+a2b2p=an mod q So if i know ai 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