# 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 ).

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.