up previous next
Chinese Remainder Theorem
CRT(R1: INT, M1: INT, R2: INT, M2: INT): RECORD |
This function combines two residue-modulus pairs
(R1,M1)
and
(R2,M2)
using the Chinese Remainder Theorem to produce a single
residue-modulus pair
(R,M)
such that
R = R1 mod M1
and
R = R2 mod M2
,
and
|R| < M
. The moduli
M1
and
M2
must be coprime (hence
M = M1*M2
).
/**/ CRT(2,3, 4,5);
record[modulus := 15, residue := -1]
|