by Carsten König

The Chinese remainder theorem

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 n_1,..,n_t (so the greatest common divisor of every two of those will be 1 – none have any common divisors) and write N = \prod_{i=1}^{t} n_i .

Now for every given integers a_1, .., a_t there is a integer X that satisfies all the congruences

X \equiv a_i (mod n_i ) .

Nice – isn’t it? But there’s more: if Y is another solution of those congruences than X \equiv Y (mod N) and every Y with Y \equiv X (mod N) solves the system too – so knowing one solution at once yield all the others (just add or subtract multiples of N 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 a,b with greatest common divisor 1, that you can find two integers x,y with 1 = ax + by.

For the facts remember that a and b should be coprime and I will recycle the integers x and y too…

Fact 1

If a divides c and b divides c then ab divides c too.

Proof

As our given numbers divides c there are integers k,l with c=ka and c=lb. Then multiplication of 1 = ax + by by c yields c = axc + byc = (xl)ab + (yk)ab = (xl+yk)ab so ab divides c.

Fact 2

Is not only a,b but also a,c coprime then a and bc are coprime.

Proof

Taking similar integers \dot{x},\dot{y} for 1 = a\dot{x} + c\dot{y} and multiplying this with 1 = ax + by yields

1 = (x \dot{x} a + x \dot{y} c + \dot{x} y b)a + y \dot{y} bc and so the gcd of a and b 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 Zwinkerndes Smiley ).

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 i both X and Y are congruent modulo a_i they are congruent to each other meaning n_i divides X-Y but then we can use fact 1 above (t-times) seeing that N divides X-Y too!

Now if X is congruent to Y modulo N than of course they are congruent modulo n_i (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 n_i’s are pairwise coprime so must be the

n_j and m_j := \frac{N}{n_j} (for each j).

And we can again find (using the extended Euclidean algorithm)  integers \lambda_j and \mu_j with 1 = \lambda_j n_j + \mu_j m_j.

Define A_j := \mu_j m_j.

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

Now it’s easy to check that

X = a_1 A_1 + .. + a_t A_t

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.