I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while preventing hitting a case where the invMod function is undefined.
Currently I am filling an array with values in a range, example: if the range is 8 the array Primes[] = {1,2,3,5,7}. Then I am replacing 1 with a randomly generated integer, in this example lets say 50. In reality the program will choose a super-large integer, somewhere in the of 100-150 digits but for simplicity lets say the array becomes Primes[]= {50,2,3,5,7}.
We then take the total product, i.e. 50*2*3... = 10500 and call it x0
A new array is then created according to pHat[i] = x0/Primes[i]... i.e. pHat[] = {210,5250,3500,2100,1500}
Now here is where the problem is:
The algorithm calls for the values in pHat to be inverse modulus with Primes. i.e.
pHat[0] invMod Primes[0] = 210 invMod 50 = undefined pHat1 invMod Primes1 = 5250 invMod 2 = undefined pHat[2] invMod Primes[2] = 3500 invMod 3 = 2 pHat[3] invMod Primes[3] = 2100 invMod 5 = undefined pHat[4] invMod Primes[4] = 1500 invMod 7 = 4
When the program initially begins it asks for the range over which the primes are picked (8 in the example) AS WELL AS how many of those primes to choose as a SECURITY KEY. In the example only 2 were defined but if the user picks 3 the program will fail. Without restricting the number of primes the user can pick, can anyone see a clever way to prevent an undefined being chosen? Below is the algorithm we are trying to use.
