Cryptography Reference
In-Depth Information
11. The result is again 7. Finally, in the fifth and last iteration, this value is squared
modulo 11. The result is 5. Consequently, 7 22 (mod 11) equals 5.
3.3.3
Chinese Remainder Theorem
One sometimes has a system of congruences for an integer that must all be fulfilled
simultaneously. This is where the Chinese remainder theorem (CRT) as captured in
Theorem 3.6 comes into play (we provide the theorem without a proof).
Theorem 3.6 (Chinese remainder theorem) Let
x
a 1 (mod n 1 )
x
a 2 (mod n 2 )
...
x
a k (mod n k )
be a system of k congruences with pairwise co-prime moduli n 1 ,...,n k . The system
has a unique and efficiently computable solution x in
Z n with n = i =1 n i .
The fact that the solution is unique in
Z n means that all other solutions are
not elements of
Z n . In fact, the set of all solutions is the set of integers y such
that y
x (mod n ). Furthermore, the fact that there is an efficiently computable
solution x in
Z n means that there is an efficient algorithm that finds the solution.
This algorithm is sometimes referred to as the Chinese remainder algorithm (CRA).
Let m i = n/n i for i =1 ,...,k ,and y i = m i (mod n i ), meaning that y i is
the multiplicative inverse element of m i modulo n i . Because all moduli are assumed
to be pairwise co-prime, y i is well defined (for all i =1 ,...,k ). The solution x can
then be computed as follows:
k
x
a i m i y i (mod n )
i =1
For example, consider the following system of 3 congruences:
x
5(mod7)
x
3 (mod 11)
x
11 (mod 13)
Search WWH ::




Custom Search