I hope to do a series covering some theory and implementation of the RSA algorithm in F# in the near future – and one of it’s main ingredients (for simplifying the hard calculations) is the Chinese remainder theorem – so let’s get back into blogging by writing a bit on it.

# The statement

As I want to show some code at the end I will state the theorem in it’s “classical” form instead of the very short ring-theoretic form – I think it’s much easier to see the value of it and of course I don’t have to introduce as much “ring”-stuff this way.

So suppose you have a bunch of pairwise coprime positive (indeed only zeros will be a problem but let’s stick with positives) integers (so the greatest common divisor of every two of those will be 1 – none have any common divisors) and write .

Now for every given integers there is a integer that satisfies all the congruences

.

Nice – isn’t it? But there’s more: if is another solution of those congruences than and every with solves the system too – so knowing one solution at once yield all the others (just add or subtract multiples of to it).

# Some small facts needed for the proof

You may want to have a look at the post on the extended Euclidean algorithm first – because both of those “lemmas” are just simply consequences of the fact that if you have two numbers with greatest common divisor 1, that you can find two integers with .

For the facts remember that and should be coprime and I will recycle the integers and too…

### Fact 1

If divides and divides then divides too.

#### Proof

As our given numbers divides there are integers with and . Then multiplication of by yields so divides .

### Fact 2

Is not only but also coprime then and are coprime.

#### Proof

Taking similar integers for and multiplying this with yields

and so the gcd of and must be 1.

##### Remarks:

Of course this is very easy if decompose the number into their prime factors – but you don’t really need it – or to be precise to proof this you will need the stuff used here.

## Proof of the theorem

The proof is now rather easy and it’s constructive (so I can give a small F#-snippet at the end ).

Let’s proof first the second part. If X and Y are solutions to the system we looked at in the first section, then because for each both X and Y are congruent modulo they are congruent to each other meaning divides but then we can use fact 1 above (t-times) seeing that N divides too!

Now if X is congruent to Y modulo N than of course they are congruent modulo (for all i) and if one is a solution the other is too.

Ok, now to the interesting part: let’s find a solution X!

Because the ’s are pairwise coprime so must be the

and (for each j).

And we can again find (using the extended Euclidean algorithm) integers and with .

Define .

Of course is congruent to 1 modulo and congruent to 0 modulo (for every other i). We see this by simply using the definition of we just gave.

Now it’s easy to check that

is a solution to our system.

## Implementing this in F#

is just a straight rewriting of the last proof-steps in code:

let nmod a b = let m = a % b if m >= 0I then m else b+m /// euclidean algorithm for finding the /// greatest common divisor (GCD) of two /// integers let rec GCD (a : bigint) (b : bigint) = if b = 0I then a else let a' = b let b' = a % b GCD a' b' /// extendet euclidean Algorithm /// Input: two integers a, b /// Output: a tripple of integers gcd, t, s /// so that gcd(a,b) = gcd = t*a + s*b let extGCD (a : bigint) (b : bigint) = let rec inner (r'', s'', t'') (r', s', t') = let step () = let q = r'' / r' let r = r'' - q*r' let s = s'' - q*s' let t = t'' - q*t' (r, s, t) if r' = 0I then (r'', s'', t'') else inner (r', s', t') (step()) inner (a, 1I, 0I) (b, 0I, 1I) /// chin. remainder theorem /// solve X = b_i (mod n_i) /// for t natural numbers n_i, /// beeing pairwise relative prime let chinRemainder ns bs = let getMs a b = extGCD a b |> (fun (_,_,m) -> m) let N = ns |> List.fold (*) 1I let Ns = ns |> List.map (fun n -> N/n) let ms = zipWith getMs bs ns let As = zipWith3 (*) bs ms Ns nmod (List.sum As) N

Here is a “test-case”:

[<Test>] member test.``for n=(2,3,5) and a=(0,2,4) ist X congruent 14``() = // ARRANGE let ns = [2I; 3I; 5I] let a's = [0I; 2I; 4I] // ACT let x = Nummerical.chinRemainder ns a's // ASSERT Assert.AreEqual(14I, x)

You can find the mini-project here.

I hope you enjoyed this – please feel free to give me some feedback on this – thanks.