Using Euclid's Extended Modular Inversion formula to solve for the CRT can be overkill in the case that the totients of the number field are already known. I present a very efficient formula that's deceptively simple. Not to mention... FAST!
Here is an example of the problem:
We have a basket of eggs. When they are grouped by 3, 2 are left over. When they are grouped by 7, 6 are left over. When they are grouped by 13, 10 are left over. What's the smallest number of eggs which will satisfy this scenario?
Our equation looks like this (where % is the modulo operator):
1> X % 3 = 2 (X divided by 3 has a remainder of 2)
2> X % 7 = 6 (X divided by 7 has a remainder of 6)
3> X % 13 = 10 (X divided by 13 has a remainder of 10)
Notice that I used prime numbers as our divisors in the calculations. This makes our formula simple because the totient of a prime is (p - 1).
After performing the CRT on equations 1 & 2, we arrive at:
X % 21 = 20 (and the totient of 21 = 12).
After performing the CRT with the last result and equation 3, we arrive at:
X % 273 = 62 (and the totient of 273 = 144).
62 is the solution because:
1> 62 % 3 = 2
2> 62 % 7 = 6
3> 62 % 13 = 10
You can now chain the output with more equations and extend it to represent very large integers.
Using the code
Calling into the method Solve will return the CRT solution of the given inputs. The only restrictions are that the input values (V1, V2) must be coprime and the totient values must be correct.
public static void Solve(BigInteger V1,
out BigInteger V3,
out BigInteger TotientV3,
out BigInteger Residue3)
if (BigInteger.GreatestCommonDivisor(V1, V2) != 1)
throw new Exception("The two parameters specified must be coprime and greater than 1.");
V3 = V1 * V2;
TotientV3 = TotientV1 * TotientV2;
Residue3 = Residue1 * V2 * BigInteger.ModPow(V2, TotientV1 - 1, V3) + Residue2 * V1 * BigInteger.ModPow(V1, TotientV2 - 1, V3);
Residue3 = BigInteger.Remainder(Residue3, V3);
Points of Interest
You can use this code to handle modular operations of very large numbers in a very efficient manner (such as in RSA and PGP modular arithmetic).