current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

I am trying to use the inverse modulus function as provided in the NTL library that can be found here: http://www.shoup.net/ntl/doc/tour.html

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. The array then 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
pHat[1] invMod Primes[1] = 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

The integer replacing 1 is randomly generated and it can be anywhere from 0 to a number with thousands of digits (pretty much any integer you can think of). 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?

share|improve this question
1  
Usually these kind of questions fare better on e.g. math.stackexchange.com . A good hint is usually if askers (i.e. you) don't specify a language or runtime and think the other tags are more important. –  owlstead yesterday

1 Answer 1

up vote 0 down vote

So lets first understand why we get undefined, while performing a modinv b we get undefined if GCD(a, b) is not equal to 1, i.e they have a common factor with each other since the random number you chose i.e, 50 has a factor with 2, 5 therefore we get undefined.

one way to avoid getting undefined would be to check if the random number you chose is not a multiple of the primes that you have considered, or an easy and even better fix would be to choose a prime number as the random number.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.