（この記事はJulia Advent Calendar 2016の21日目の記事です）
二次数体ふるい法を実装してみた
Juliaというプログラミング言語には興味を持っていたのだが、特に興味を持ったきっかけは、この記事にあるように、Polland-Rho法による素因数分解が標準装備されているという点である。
ということで、Juliaを触りだすきっかけとして、自分でも素因数分解ルーチンを作ってみようと思い、二次数体ふるい法を実装してみた。
そのソースコードがこちら：
https://github.com/hamukazu/quadratic_sieve
といってもまだ全然ダメで、一応正しい答えが出てくることは確認したが、Julia標準の素因数分解より数倍遅い。これはまだアルゴリズムをよく理解してなくてチューニングパラメータがよくわからないことと、Juliaのパフォーマンス・チューニングがよくわからないのが原因である。これから改良していきたい。
初めてJulia書いてみた感想
文法規則はシンプルだし、学習コストはそれほど高くなかったと思う。コードを書いていて一番苦労したのが、エラーメッセージが不親切な点。特にランタイムエラーが出てきたときに、何行目で起こっているかがわからなくて、デバッグ用の@showを書きまくって解決したのだが、これはなんとかならないだろうか。
参考文献
Juliaの文法はこの本で学習した：
Mastering Julia
この本一冊読めば十分かと思う。
二次ふるい法については、考案者Pomeranceによる解説が役にたった。
C.Pomerance, Smooth numbers and the quadratic sieve, Algorithmic Number Theory, 2008
またこの解説論文（大学の講義資料）も役に立った。
E.Laquist, The Quadratic Sieve Factoring Algorithm, MATH 488: Cryptographic Algorithms, University of Virginia, 2001