Merkle-Hellmanナップサック暗号
Merkle-Hellmanナップサック暗号は、シャミアにより多項式時間で解読できることが示されている。
n ビットの平文
α = (α1, α2, ..., αn )
を暗号化する。ここで、各 αi は第i ビットを表す (αi ∈{0,1})。
c = ∑ i = 1 n α i β i {\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}}
を計算し、c を暗号文とする。