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.
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…
If divides and divides then divides too.
As our given numbers divides there are integers with and . Then multiplication of by yields so divides .
Is not only but also coprime then and are coprime.
Taking similar integers for and multiplying this with yields
and so the gcd of and must be 1.
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 .
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.