Valer BOCAN’s Web Log

I have just installed Internet Explorer 8 Beta 1 and noticed the cool coloring that happens in the address bar. Although this is a “nice-to-have” feature, it basically means that regular users may spot a phony website in a blink of an eye. Yes, provided that they have the eyes and the brains to judge that.

As I was working to implement the scalable distribution system I envisioned here, I needed a way to find the solution of a system of linear congruencies in the form of the Chinese Remainder Theorem.

Theory

Given a set of simultaneous congruencies

X ≡ Ai (mod mi)

for I = 1,…, r and for which the mi are pairwise relatively prime, the solution of the set of congruencies is

X = A1 * B1 * M / m1 + … + Ar * Br * M / mr (mod M)

where M = m1 * m2 * … * mr

and the bi terms are determined from bi * M / mi ≡ 1 (mod mi).

For instance, the set of congruencies:

X ≡ 3 (mod 27)

X ≡ 4 (mod 13)

X ≡ 2 (mod 11)

has the solution X = 2136.

C# Implementation

This is a screenshot of the code that solves the system equation above:

Here is the C# code for finding the solution of the Chinese Remainder Theorem. The code I wrote in C# also uses the code I published in a previous blog post.

Implementation of cryptography products often requires solving linear congruencies. Although the background theory is not complicated, actual implementation in a high-level language may not be straight-forward. Having the need for a linear congruence solver myself and because I could not find a decent C# implementation, I decided to share this piece of code with my readers. I included some theory stuff for your convenience.

Linear Congruence Theorem

If A and B are any integers and N is a positive integer, then the congruence

Ax ≡ B (mod N)

has a solution for x if and only if B is divisible by the greatest common divisor of A and N. When this is the case, and x0 is one solution of the congruence, then the set of all solutions is given by:

{ x0 + k * n / d } where k is a integer.

In particular, there will be exactly d = gcd(a,n) solutions in the set of residues {0,1,2,…,n-1}.

Examples

14x ≡ 5 (mod 55) has a single solution x = 20, as gcd(14, 55) is 1.

2x ≡ 4 (mod 34) has two solutions x=2 and x=19. Greatest common divisor of 2 and 34 is 2, therefore the congruence has two solutions.

Solving Linear Congruencies

In general solving equations of the form:

Ax ≡ B (mod N)

If the greatest common divisor d = gcd(A, N) divides B, then we can find a solution x to the congruence as follows: the extended Euclidean algorithm yields integers r and s such r * A + s * N = d. Then x = r * B / d is a solution. The other solutions are the numbers congruent to x modulo n/d.

For example, the congruence

2x ≡ 4 (mod 34)

has 2 solutions since gcd(2, 34) = 2 divides 4. The extended Euclidean algorithm gives (1)*2 + 0*34 = 2, i.e. r = 1 and s = 0. Therefore, one solution is x = 1*4/2 = 2. All other solutions are congruent to 2 modulo 17. Since the original equation uses modulo 34, the entire solution set in the range from 0 to 34 is x = {2, 19}.

C# Implementation

The LinearCongruence class is built using three parameters passed to the constructor: A, B and N corresponding to the terms of the congruence. The only public method is Solve which attempts to find the entire class of solutions. If no solutions are found, an exception is thrown.

Here is the output for linear congruence 2x ≡ 4 (mod 34):

The C# code is available here. I compiled it using Visual Studio 2008 Beta 2, but it should work with any other older C# compiler or with Mono. Hope this helps.

Some of the older devices that work with flash-type memory cards (like for instance digital cameras) may not fully support the recent higher capacity cards that appeared on the market. I happened to learn this the hard way, after I borrowed an old HP PhotoSmart 735 digital camera to take photos in my vacation, following the unexpected death of my good old Canon camera. The HP camera manual stated that the largest SD card known to work at the time of printing was 256MB but chances were that larger capacity cards would work as well. I decided to purchase a Kingston 2GB card, but to my surprise the camera displayed several messages that indicated that something was wrong with the formatting of the card and proceeded with the format. The net result was that somehow the camera has created a 1GB partition on my 2GB card and still refused to work properly after this.

The image above is what my computer reads about the 2GB SD card when connected to a card reader. I eventually gave up the idea of using the card with the old digital camera and purchased another 1GB card for that purpose. Now I had to find a way to reclaim the “lost” space on the original card. I tried to handle the partition using the Disk Management feature of Windows, but that did not help too much.

Here is where the DiskPart utility (which comes with Windows Vista) may help. What we need to do is actually destroy the partition table and let Windows recreate it from scratch. Here is what you need to do:

STEP 1 - Launch the DiskPart utility

You need to open a Command Prompt window then type diskpart.exe and the following window should appear. At the DISKPART> prompt, type HELP to obtain the list of commands supported by the utility. While DiskPart may not be as easy to use as similar disk-partitioning tools on the market (such as Partition Magic), it is quite powerful and best of all… it’s free.

STEP 2 – List the disks available on your system

At the command prompt, type LIST DISK. You will get the list of the disks available on your system. In my case, Disk0 is the physical disk of my laptop and the rest of the disks (1 through 4) come from the USB card reader. The disk we are interested in is Disk 1, which holds the SD media. We can see that the list shows the true size, no matter how the disk is partitioned.

STEP 3 – Select the desired disk

You need to select the disk on which subsequent operations will be performed. In this case I selected disk #1, as shown by the LIST DISK command. Make sure you select the correct disk, otherwise you may end up destroying your valuable data.

STEP 4 – Clear the partition information off the flash card

Type CLEAN at the command prompt to delete the bogus partition information created by the device (in my case the old HP digital camera). You may now exit DiskPart.

STEP 5 – Create a new partition on the flash card

Right-click Computer, then choose Manage. This will bring up the Computer Management window where you have to select Disk Management under the Storage section. Locate the disk you have previously dealt with (in my case Disk 1) and notice that the entire disk space is not allocated. Right-click the disk and choose New Simple Volume… then follow the indications of the wizard that appears. This will create a new partition on the flash disk and will optionally format it. At this point, the disk is ready to be used with its full capacity.

Hope this helps.