暗号化はNP完全問題に基づいていない

この記事では、暗号化がNP完全問題に依存しない理由を説明しています。NP完全問題は迅速に解くのが難しいですが、暗号化に必要なのは平均的に難しい問題、つまりランダムに選択されたインスタンスが解きにくい問題です。RSAはその一例で、大きな数の素因数分解の困難性に依存しており、平均的に難しいです。NP完全問題は最悪の場合の困難性しか保証せず、平均的な困難性を保証しないため、暗号化には適していません。