On the Subject of Chinese Remainder CM

China.

If the Submit Button is white, follow the instructions under Encrypt Instructions. Otherwise follow the instructions under Decrypt Instructions.

Take note: Some parts of this cipher use A1Z26 (normal alphabetic position) while some use A1Y25Z0 (normal for A–Y, but Z is 0).

Decrypt Instructions

Append any letters on screen 2 to the end of your existing encrypted word.

Start with a value v of 0 (zero). Then, for each letter in the encrypted word, multiply v by 26 and add the A1Y25Z0 value of the letter.

For each letter on screen 1:

• Convert the letter into a number using A1Z26 and add 26.
• Take v modulo that number.
• Convert the result back to a letter using A1Z26.

The letters obtained this way form the decrypted word.

Encrypt Instructions

Convert each letter on screen 1 into a number using A1Z26 and add 26. These numbers are called the moduli.

Convert each letter of the encrypted word using A1Z26 and add the A1Y25Z0 value of the corresponding letter on screen 2. Call these the remainders.

Find the only integer v in the range 0 ≤ v < p (p is the product of all the moduli) such that taking v modulo each of the moduli results in the corresponding remainders. (This number is unique per the Chinese Remainder Theorem.) The following section outlines one possible method for finding this integer.

Finding v from two moduli and remainders

This method will be explained with an example using two moduli, and subsequently, two remainders.

• v % 247 = 31
• v % 651 = 35

Begin with the congruence of the larger modulus, v % 651 = 35. Rewrite this congruence as an equivalent equation. v = 651×a + 35, for any integer a

Substitute v = 651×a + 35 into the congruence equation of the lower modulus and rewrite it with the modulo on the right. For this example, it will be 651×a + 35 = 31 ( % 247 )

Then, solve the congruence for a, so for this example, we subtract 35 from both sides, making the equation 651×a = -4 ( % 247 ). Now, repeatedly add 247 to the right until it is divisible by the multiplier of a, in this case, 651 (we do not need to worry about the left hand side because x + 247 mod 247 is the same as x mod 247). Then, divide the total by the multiplier of a, in this case, 651. In this case, we need to repeatedly add it 58 times, then after dividing, we get a = 22 ( % 247 ). Rewrite this as an equivalent equation. a = 247*b + 22, for any integer b

Then, substitute a into the first congruence equation, v = 651×a + 35, so it becomes v = 651×(247×b + 22) + 35. Then, expand this equation, making it v = 160797×b + 14357. At this point, make b zero, and calculate v at that point. That is your final value.

From the overall v, reconstructing the original word:

Once v is found, reconstruct the original word as follows:

• Take v modulo 26 and convert the result to a letter using A1Y25Z0.
• Prepend this letter to the front of previously decrypted letters.
• Divide v by 26, rounding down.
• Repeat this process until v is zero.