Merkle-Hellmanナップサック暗号
暗号文c を受け取った後、 c' = c r mod q を計算する。ここで、r は、(mod q) の整数の合同における r の逆元である。
すると、c' はw の部分和になっている。w は超増加列なので、{1,2,...,n} の部分集合S を次のようにして簡単に求めることができる。
まず、c' とwn の大小を比較し、もしc' がwn 以上の場合には、平文の第n ビットは 1 であり、小さい場合には、0 である。c' が大きい場合にはwn を減算して、次にwn-1 との大小を比較し、同様に第n-1 ビットを決める。これを第1ビットまで繰り返せばよい。
具体的なアルゴリズムは、次のとおりになる。
入力: w (超増加列), c' 出力: {1,2,...,n} の部分集合S
sをc' とし, S を空集合とする。
i = n, n-1, ..., 2, 1 について次文を繰り返す。 s≥wi ならば、s=s-wi とし、S=S∪{i} とする。
s が 0 ならばS を, 0 でないならば⊥を出力する。