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.