Shorのアルゴリズムとサマーウォーズ

サマーウォーズ見てきた。内容はなんかリア充から見たIT土方SFというか。
割とネタばれです。サマーウォーズ見てない人は見ないほうがいいかも。

内容はともかく主人公が素因数分解してる風なシーンがあったのがすごく気になった。
つか、最初の方の電車の中で彼が読んでる本がShorの素因数分解の本というのがいかにもな前フリだが。

前フリがあったにも関わらず、手計算で2056桁もある数を素因数していてびっくりした。
暗算して解いてるシーンもあったし。
素因数分解ってNP完全じゃなかったっけ。
しかもそんな彼ですら数学オリンピック代表漏れとか。
超人オリンピックですね！

上にはどんだけすごい人がいるんだというかそもそも有限時間で人間の手で解けちゃうとかそんな危ないもんが鍵になってるのかと思うと不安になる。
まぁ映画だから誇張された表現だと思いたいｗ

ということでShorのアルゴリズムを調べる。
http://blogs.yahoo.co.jp/cat_falcon/10371508.html
周期をみつけて1/2周期乗±1したのが解（の一部）ってことか！
わかりません。元のXはなんですかとかgcdってなんですかとか。

サマーウォーズに出てきたネタは実現可能そうな面白そうなのから、
そんなんぜってー無理だろ的な物まで織り交ぜてあるので
かたっぱしからJavaScriptとかP55あたりで再現してみたらおもしろいかも。