素因数分解は，RSA暗号解読より真に難しいか？

摘要

RSA暗号は，大きな合成数の素因数分解の困難さに安全性の根拠を置いている．しかしながら，素因数分解とRSA暗rn号の解読の難しさの関係に関しては，いまだ完全には解決されていない．近年，部分的な解決として，秘密鍵を求めるrnことと素因数分解を行うことの厳密な意味での等価性が証明された．具体的には，RSA暗号における秘密鍵dを求めるrnことができれば，法Nの素因数分解が決定性多項式時間で可能であることが示された．従来は，確率的，もしくは数学rn的に未解決な問題の正しさを仮定した上での決定性アルゴリズムしか知られていなかった．