Juliaで素因数分解してみた

投稿者: | 2016年12月21日

(この記事は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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です