China 
Africa 
Explore chapters and articles related to this topic
Public-Key Encryption
Published in Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography, 2020
Using Chinese remaindering. In implementations of RSA-based encryption, the receiver can use the Chinese remainder theorem (Section 9.1.5) to speed up computation of eth roots modulo N during decryption. Specifically, let N = pq and say the receiver wishes to compute the eth root of some value y using d = [e−1 mod ϕ(N)]. The receiver can use the correspondence [yd mod N] ↔ ([yd mod p], [yd mod q]) to compute the partial results () xp:=[ydmodp]=[y[dmod(p−1)]modp]
Basics of Number Theory
Published in Sriraman Sridharan, R. Balakrishnan, Foundations of Discrete Mathematics with Algorithms and Programming, 2019
Sriraman Sridharan, R. Balakrishnan
Suppose there is more than one linear congruence. In general, they need not possess a common solution. (In fact, as seen earlier, even a single linear congruence may not have a solution.) The Chinese remainder theorem ensures that if the moduli of the linear congruences are pairwise coprime, then the simultaneous congruences all have a common solution. To start with, consider congruences of the form x≡bi(modmi) $ x \equiv b_i\, \pmod {m_i} $ .
Efficient Implementation
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
Fact 2.120 introduced the Chinese remainder theorem(CRT) and Fact 2.121 outline da nalgorithm for solving the associated system of linear congruences. Although the method described there is the one found in most textbooks on elementary number theory, it is not the method of choice for large integers. Garner’s algorithm (Algorithm 14.71) has some computational advantages. §14.5.1 describes an alternate (non-radix) representation for nonnegative integers, called a modular representation, that allows some computational advantages compared to standard radix representations. Algorithm 14.71 provides a technique for converting numbers from modular to base b representation.
The power of the snake: number theory with Python
Published in International Journal of Mathematical Education in Science and Technology, 2022
Modular inverses are used prominently when solving systems of congruences. The standard solution method uses the Chinese Remainder Theorem, whose constructive proof (Burton, 2010, p. 79) requires students to work on several examples before they fully understand it. Using the auxiliary prod and modinv functions from previous sections, the actual Python code without comments is only six lines long3:
A Comparative Review on Homomorphic Encryption for Cloud Security
Published in IETE Journal of Research, 2021
Ganesh Kumar Mahato, Swarnendu Kumar Chakraborty
Pascal Paillier, in 1999, invented the Paillier encryption algorithm. It is based on composite residuality classes and a probabilistic key-scheme [19]. It uses the Chinese Remainder Theorem to decrypt the cipher text to the original message.