素因数分解は,RSA暗号解読より真に難しいか?
Vol.91 No.6pp.474-477
発行日:2008/06/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特 集素数
専門分野:
本文:PDF(417.3KB)>>
あらまし:
RSA暗号は,大きな合成数の素因数分解の困難さに安全性の根拠を置いている.しかしながら,素因数分解とRSA暗号の解読の難しさの関係に関しては,いまだ完全には解決されていない.近年,部分的な解決として,秘密鍵を求めることと素因数分解を行うことの厳密な意味での等価性が証明された.具体的には,RSA暗号における秘密鍵dを求めることができれば,法Nの素因数分解が決定性多項式時間で可能であることが示された.従来は,確率的,もしくは数学的に未解決な問題の正しさを仮定した上での決定性アルゴリズムしか知られていなかった.