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.