代表的な公開鍵暗号であるRSA暗号に関する未解決の問題として、
それを解読する難しさが素因数分解と同じであるかどうかを示す
という問題がある。
紹介する論文では、RSA暗号解読アルゴリズムと代数演算を利用
した素因数分解の効率的アルゴリズムが存在したとしても、その
アルゴリズムを代数演算だけを利用する効率的アルゴリズムに
変換できることを示してある。
これにより、代数演算のみによる素因数分解に限れば、RSA暗号
を効率的に解読することと素因数分解を効率的に行うことの
難しさが等価でないことがわかる。
Back