Chinese Remainder Theorem (CRT)

CRT is used to speed up modulo computations by computing smaller moduli \(m_i\) in the Set \(\mod M = m_1 m_2 \ldots m_3\) instead of full modulus \(M\).

For example, to compute \(A (\mod M)\):

Do a Prime Factorisation on \(M\) to find out \(m_i\)
Calculate \(M_i = M / m_i\)
List a set of linear congruences using \(M_i b_i = 1 (\mod m_i) \rightarrow r_i b_i\) where \(r_i\) is \(M_i \mod m_i\) and find out the inverse# \(r_i^{-1}\) which is \(b_i\) at the same time
Knowing \(c_i\) is actually \(M_i b_i\), sums up the result with \(A \equiv (\sum_{i=1}^k a_i c_i) (\mod M)\)

Links to this page

TAC3121 Chapter 2: Finite Fields and Computational Number Theory

Chinese Remainder Theorem (CRT)
Rivest-Shamir-Adleman (RSA)

From here, we could get the public key \(pu = \{e, n\}\) and private key \(pr = \{d, n\}\). Encryption could be done on message \(M\) using the formula \(C = M^e \mod n\) where \(0 \le M < n\) by using public key \(pu\) which is typically done by Square-and-Multiply Algorithm# for efficiency. Decryption could be done on ciphertext \(C\) using the formula \(M = C^d \mod n\) by using private key \(pr\) which is usually done by Chinese Remainder Theorem (CRT)#.

Note: \(e\) is usually relatively small or \(65537_{10}\) which is \(10000000000000001_2\) for easy computation by Square-and-Multiply Algorithm#. That being said, \(e\) can’t be either 1 or 2. The former means no encryption is done on \(M\) as \(M^e = M^1 = M\). The latter will not work due (\(d\) not exist) to the nature of Greatest Common Divisor (GCD)# since \(GCD(2, \phi(n))\) will always be 2 as \(\phi(n) = (p - 1) (q - 1)\) where \(p\) and \(q\) are primes results in even number. However, if \(e\) is too small, it is vulnerable to mathematical attack using Chinese Remainder Theorem (CRT)#.

#math #review