Editing Merkle–Hellman knapsack cryptosystem (section)

===Decryption===
To decrypt a ciphertext <math>c</math>, we must find the subset of <math>B</math> which sums to <math>c</math>. We do this by transforming the problem into one of finding a subset of <math>W</math>. That problem can be solved in polynomial time since <math>W</math> is superincreasing.

1. Calculate the [[modular inverse]] of <math>r</math> modulo <math>q</math> using the [[Extended Euclidean algorithm]]. The inverse will exist since <math>r</math> is coprime to <math>q</math>.
:<math>r' := r^{-1} \pmod q</math>
:The computation of <math>r'</math> is independent of the message, and can be done just once when the private key is generated.

2. Calculate
:<math>c' := c r' \bmod q</math>

3. Solve the subset sum problem for <math>c'</math> using the superincreasing sequence <math>W</math>, by the simple greedy algorithm described below. Let <math>X = (x_1, x_2, \dots, x_k)</math> be the resulting list of indexes of the elements of <math>W</math> which sum to <math>c'</math>. (That is, <math>c' = \sum_{i=1}^k w_{x_i}</math>.)

4. Construct the message <math>m</math> with a 1 in each <math>x_i</math> bit position and a 0 in all other bit positions:
:<math>m = \sum_{i=1}^k 2^{n-x_i}</math>

====Solving the subset sum problem====
This simple greedy algorithm finds the subset of a superincreasing sequence <math>W</math> which sums to <math>c'</math>, in polynomial time:

:1. Initialize <math>X</math> to an empty list.

:2. Find the largest element in <math>W</math> which is less than or equal to <math>c'</math>, say <math>w_j</math>.

:3. Subtract: <math>c' := c' - w_j</math>.

:4. Append <math>j</math> to the list <math>X</math>.

:5. Remove <math>w_j</math> from the superincreasing sequence <math>W</math>

:6. If <math>c'</math> is greater than zero, return to step 2.