Crpytoanalysis of Merkle-Hellman Knapsack algorithm

Hi,

I don't know whether this is the kind of explanation you are expecting, but here goes:
If you look at the equation, it simply means that q is a number (integer in this case) which when multiplied by 15 and divided by 17 leaves 1 as remainder.

Manually, we needs to start counting from 1 onwards.
e.g.
(15*1) mod 17 = 15 mod 17 = ((17*0)+15) mod 17 = 15
(15*2) mod 17 = 30 mod 17 = ((17*1)+13) mod 17= 13
(15*3) mod 17 = 45 mod 17 = ((17*2)+11) mod 17 = 11

If you count in this manner, you'll see that the first number where the required condition (1 as remainder) is met is when q=8.
(15*8) mod 17 = 120 mod 17 = ((17*7)+1) mod 17 = 1

Speaking from the programming perspective, you can use the q as variable and state the equation as the condition which needs to be met, you'll get the same answer.

Hope this helps.

Warm regards,
Sarang

Yes but the fact is that I can't continue to test every possible number till i get a 8

am trying to derive a faster way of getting q.

because i am going to be dealing with larger interger values and it won't be possible for me to do that for all the values

( 15 * q ) mod 17 = 1
q = 15^(-1) mod 17; i.e., q is the modulo multiplicative inverse of 15 mod 17
Since 17 is prime (and therefore 15 and 17 are mutually prime, then we know that there exists a solution to this problem.

Here is an introduction to Modular multiplicative inverse:
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Here is code from http://snippets.dzone.com/posts/show/4256 on computing efficiently the modulo inverse (I did not test it):

int modInverse(int a, int n) {
 int i = n, v = 0, d = 1;
 while (a>0) {
  int t = i/a, x = a;
  a = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 }
 v %= n;
 if (v<0) v = (v+n)%n;
 return v;
}

Select allOpen in new window

Thanks for the input , but I am actually working this as a maths fomular with pen , paper and calculator and not writing a program

After getting problem in correct form, here is link showing Pen, paper, calculator example:
http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html#Modular-GCD

I'll be back later if you still need assistance.

good