Click here to Skip to main content
Click here to Skip to main content

Solving the Chinese Remainder Theorem Using Totients

, 2 Sep 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

 

        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)

Share

About the Author

Cryptonite

United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 5 PinprofessionalVolynsky Alex7-Sep-14 11:52 
GeneralRe: My vote of 5 PinmemberCryptonite25-Sep-14 9:37 
GeneralRe: My vote of 5 PinprofessionalVolynsky Alex25-Sep-14 10:38 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 3 Sep 2014
Article Copyright 2014 by Cryptonite
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid