k-threshold system of deciphering N

k-threshold system of deciphering N

This programme is an application of the Chinese Remainder Theorem for Integers - for obtaining a solution to the "k-threshold system for sharing a secret". The concept is explained in the book "A course in Number Theory and Cryptography by Neal Koblitz" in Ch 1, Prob 24 / P27 and it's solution in P205.

Let me explain the problem with some specific numbers.

Let N = 4333621567 be a secret number known completely ONLY to the Commanding General for unlocking a missile system. Let there be 9 Lt Gens under him who are each given some partial info related to N. If the General is incapacitated, we want that ANY "k" Lt Gens (k >= 3) (out of the total of 9 Lt Gens) should be able to decipher N by processing their combined partial infos. Also, information available with just (k-1) Lt Gens should not be able to decipher N.

Now the problem to be solved is :

a) if k = 3, ie, if ANY 3 Lt Gens should be able to make the decision, what is partial info that should be given to each of the 9 Lt Gens
so that they (ANY 3) can combine to decipher N?

b) if k = 5, ie, if ANY 5 Lt Gens should be able to make the decision, what is partial info that should be given to each of the 9 Lt Gens
so that they (ANY 5) can combine to decipher N ?

I developed this programme to answer exactly these 2 questions.

In this programme, the variable k_thrsh represents the "threshold k". Refer to Usage Eg Case 6 for k (k_thrsh) = 3 and Usage Eg Case 5 for k_thrsh = 5.

This programme calls my code Ch_Rem_Thr_Int.m for solving the k number of simultaneous congruence equations. Since Matlab has a Precision limit of 16 digits, we will not get correct results whenever this limit is crossed in the intermediate calculations.

A "Mathematical Proof" linking N to (different) mk and ck sets is what I am looking for. I will be glad if someone can mail me the Proof or links to the Proof. See Q N4 below.

Q N4 : How is it that mk set formed of ANY k_thrsh primes within the band of sqrt(N) and N^(1/k_thrsh) (and it's corresponding residue ck with mod N) results in the correct deciphering of N?

I understand that once mk and ck are given, the Chinese Remainder Theorem will calculate the correct solution c_soln.

But what I would like to have is a "Mathematical Proof" for :

a) Why should mk set of coprimes fall within the above band ?

b) How ANY set of k_thrsh primes in the above band gives the correct solution ?