Solving the Chinese Remainder Theorem Using Totients

• Download CRTTestHarness-noexe.zip - 16.9 KB
• Download CRTTestHarness.zip - 16.9 KB

Introduction

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!

Background

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,
    BigInteger TotientV1,
    BigInteger Residue1,
    BigInteger V2,
    BigInteger TotientV2,
    BigInteger Residue2,
    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.");
    }

    //we will trust that the user supplied the correct totient values from here
    V3 = V1 * V2; //we will reduce everything to this new modulus
    TotientV3 = TotientV1 * TotientV2; //the totient of our new modulus

    //our simple CRT equation:
    //Residue3 = Residue1 * V2 * [V2^(TotientV1 - 1) % V3] + Residue2 * V1 * [V1^(TotientV2 - 1) % V3]

    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).