« G社の会社説明会の参加受付完了 | メイン | E社の技術職向けセミナー申し込み »
2005年02月18日
引き続き情報セキュリティ特論のレポート
情報セキュリティ特論のレポート締め切りがいよいよ近づいてきましたがまだ終わりません。残り2つの課題のうち4つ目に取り組んでいます。その過程で大きな合成数を素因数分解する必要がでてきました。350ビットもあるので、さすがに順番に素数で割っていくという力任せの方法では無理。実は試しに昨日の夜帰宅する前にプログラムを仕掛けていったんですが、一晩かけても終わりませんでした……。
そんなわけでより効率的なアルゴリズムを使って求めることにしました。素因数分解のアルゴリズムには連分数法や楕円曲線法(ECM)、複数多項式2次ふるい法(MPQS)、数体ふるい法(NFS) など色々ありますが、今回は自分で組むのも面倒なのでMPQSを使ったプログラムを拾ってきて使わせてもらうことにします。その結果、Pentium 4マシンで10分少々で求まりました。途中メモリが足りずスワップが起きていたようなので、それがなければ10分切れたかも。
これで4つ目の課題の目処も付いたので、残すはあと1つ。何とか週末で終わらせないと。
投稿者 sai : 2005年02月18日 00:49