In public-key Cryptography, especially with the RSA algorithm, the Chinese Remainder Theorem is often used. Say you have a system of simultaneous congruences as follows

x a₁ mod m₁
x a₃ mod m₂

x a_k mod m_k ,

where m₁, m₂, ..., m_k are coprime, i.e. gcd(m₁, m₂, ..., m_k) = 1. How can we solve for x? The solution is quite straight forward, but could involve a fair amount of calculations. I find that breaking down the method into smaller steps makes it easier to find and fix mistakes. By the Chinese Remainder Theorem, the solution to that system of equations is

x = (a₁M₁y₁ + a₂M₂y₂ + ... + a_kM_ky_k) mod M ,

where M_i is the product of all m's except for m_i

,

y_i is the multiplicative inverse of M_i modulo m_i

y_i M_i^-1 mod m_i ,

and M = m₁ * m₂ * ... * m_k .

Let us try a numeric example. Here is a system of simultaneous congruences:

x 12 mod 25
x 9 mod 26
x 23 mod 27

We start by calculating M₁ and y₁:
M₁ = m₂ * m₃ = 26 * 27 = 702
y₁ = M₁^-1 mod m₁ = 702^-1 mod 25 .

We apply the Extended Euclidean Algorithm to find the multiplicative inverse of 702 relative to 25:
702 = 28 * 25 + 2 → 2 = 702 – 28 * 25
25 = 12 * 2 + 1 → 1 = 25 – 12 * 2
                                = 25 – 12 * (702 – 28 * 25)
                                = 337 * 25 – 12 * 702

Then y₁ = 702^-1 mod 25 -12 13.

The same calculations can be carried on to find M₂ = 675, y₂ = 25, M₃ = 650 and y₃ = 14. Now it is just a matter of plugging in the values into the equation:

x = (a₁M₁y₁ + a₂M₂y₂ + a₃M₃y₃) mod M
= (12*702*13 + 9*675*25 + 23*650*14) mod 17550 470687 14387

To verify our answer we can plug that number back into the system:

470687 mod 25 12
470687 mod 26 9
470687 mod 27 23

Related links (constantly updated):

• March of the monks
• Photographs from the Burma Protests
• Myanmar troops kill 9 protesters - Reuters
• Nine killed in Burmese crackdown - BBC
• Canadian friends of Burma
• US Campaign for Burma
• Burma Campaign UK

I was told that HostingIt365's webserver was hit by a DoS attack and their DNS file got corrupted. I had to change servers twice in the past week; depending on your location, pensador.org could be pointing to three different copies of this website. I will wait until the DNS records get replicated worldwide and then I will try to synchronize the data between them.

This Monday I had yet another renal calculus crisis—the second one in less than 12 months. There was I, in the emergency section of the local hospital contorting in pain from 18:30 to 22:30. By 23:00 the stone had moved from my ureter to my bladder, which reduced the pain, and by the next day it finally got expelled from my system. After a blood test and an x-ray, the doctor said I had to drink more water and reduce the salt in my diet. I am considering taking Herba Desmodii capsules, a natural diuretic, which a co-worker said does wonders to kidney stones.

Here's a little Bossa Nova for you to listen to when you get home from work. Just sit back and relax. I wanted to give YouTube's custom players a try—I've put together this playlist with my favourite Bossa Nova videos.