限定算術における素因数分解問題

スポンサーリンク

概要

論文の詳細を見る
論理体系 S^1_2 において Σ^b_1 クラスで定義可能である関数全体の集合は、多項式時間で計算可能な関数全体の集合 PF に等しいということが一般に知られている。二つの素数 p, q の積 pq からその素数を割り出すアルゴリズムは、未だ発見されていない-つまりその演算を S^1_2 において Σ^b_1 クラスで定義することは、かなり難しいわけであるが、S^1_2 にある公理を付け足すと、それが可能になる。仮に、体系 S^1_2 自身がその公理を証明できれば、RSA のシステムはもはや安全ではなくなるが、幸か不幸か、そういうことはありそうもない。
1997-09-12

著者

関連論文

スポンサーリンク