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.
Entries (RSS)