Click here to Skip to main content
15,867,488 members
Articles / Security / Cryptography
Tip/Trick

Solving the Chinese Remainder Theorem Using Totients

Rate me:
Please Sign up or sign in to vote.
5.00/5 (4 votes)
2 Sep 2014CPOL2 min read 16.8K   131   2   4
This code gives a solution to the Chinese Remainder Theorem using totients instead of the Extended Euclidean algorithm.

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.

 

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

 

 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionMy vote of 5 Pin
sbarnes9-Dec-15 15:57
sbarnes9-Dec-15 15:57 
Such a short little article. Deceptively deep. Makes my mouth water for application. Thank you very much.

GeneralMy vote of 5 Pin
Volynsky Alex7-Sep-14 10:52
professionalVolynsky Alex7-Sep-14 10:52 
GeneralRe: My vote of 5 Pin
Cryptonite25-Sep-14 8:37
Cryptonite25-Sep-14 8:37 
GeneralRe: My vote of 5 Pin
Volynsky Alex25-Sep-14 9:38
professionalVolynsky Alex25-Sep-14 9:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.