02/08/09 19:13 o+8My8IY
カンプールのインド工科大学のManindra Agrawal、Neeraj KayalおよびNitin Saxenaが、
素数判定を多項式時間(polynomial time)で可能なアルゴリズムを発見、証明した。
素数判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
影響を及ぼすと予想される。
論文は以下のURLからたどることができる。
また、ニューヨークタイムズの記事によると、ベル研のDr. Carl Pomerance博士は
この論文を正確(correct)であると断定し、「このアルゴリズムは美しい。」
("This algorithm is beautiful.")とコメントしたという。
論文のURL(英語: 数学者の写真あり): URLﾘﾝｸ(www.cse.iitk.ac.in)
NY Timesの記事(英語): URLﾘﾝｸ(www.nytimes.com)
関連スレ
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
ｽﾚﾘﾝｸ(newsplus板)
素数判定は「決定的」多項式時間で可能
ｽﾚﾘﾝｸ(math板)
もうだめぽ、、