Pensador’s Blog

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

I was getting really frustrated with the fact that I had to copy and paste the character ç whenever I had a conversation with someone from Brazil. I did a search around the Ubuntu forums to realize that I was not the only one having this problem. The thing is that on Windows, when you type single quote and c, you get a c cedilla (ç). On Ubuntu, you get a c acute (ć).

If you are in the same boat, here is how I solved my problem.

1. Add “U.S. English International (with dead keys)” to your list of layouts (System > Preferences > Keyboard).
2. On the Layout Options tab, make sure the Alt key is a third level chooser.
3. Alt+, gives the desired results.

Here is how to save YouTube videos to your computer using FireFox:

1. Clear the FireFox cache:
   Tools > Options… > Privacy > Cache > Clear Cache Now
2. On FireFox, open the location about:cache.
3. Open the Cache Directory path on Windows Explorer.
4. Go to the page of the video that you want to download.
5. Refresh the cache directory (Ctrl-R).
6. You should see a new file that appears. Create a copy of it and add the extension “.flv”.
7. Open the file with FLV Player.

I know there are programs that do the job much better but I like it the dirty way: batch files.
It’s fast, no installation required and does what I want. Enough talk, here is the code:

@dir %1 /w /b /o:gn > "_listing.txt"

Copy the code to a text file and change its extension to .bat
/b - bare format, remove this for detailed info
/o:gn > “_listing.txt” - sends the output to “_listing.txt”

For further customization, type dir /? on a command prompt.