素数判定が多項式時間で！
タレコミ by moonbear
moonbear 曰く、
すでに多くの方がタレこんでいらっしゃるかも知れませんが，Indian Institute of Technology Kanpur の Agrawal 教授らのグループにより， 多項式時間で素数判定ができるアルゴリズムが開発 されたそうです．論文もあります（Peer review 等がされているのかどうか定かではないのですが）．もっとも，これは素数判定であって素因数分解ではないので，実際に今使っている暗号のアルゴリズムがすぐにだめになるわけではないのですが．それでも久々にわくわくするニュースではあります．