あらまし

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

國廣　昇 

Vol.91 No.6pp.474-477

発行日:2008/06/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特　集素数

専門分野:

キーワード:
素因数分解, RSA暗号, 計算量の等価性, 

本文:PDF(417.3KB)>>

記事を購入

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

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355

…ジュニア会員・学生員に
　お勧めの記事