されている主要な素因数分解アルゴリズムは、大きく分けて群論系とふるい系に分かれます。method)はその何れにも属さない少々特殊なアルゴリズムです。名前も特殊で、他のアルゴリズムはその理論的特徴から命名されていますが、ρ法は処理の流れを図にしたときに、ギリシャ文字のρ(ロー)に似た形になることからそのように呼ばれています。method)と呼ばれたりもします(註1)。対象合成数Nの素因数pを発見するため計算量が、Nの大きさよりはpの大きさに依存するという特性があります。そのため、巨大な合成数Nを他のアルゴリズムで素因数分解するための前処理として比較的小さな素因子を取り除いておく目的にも使われます。Nが乱数に近い振る舞いをするような整数列とします。x2iで定まる数列とします。このとき、当然の事ながらgiはNの因数です。それは自明な因数1,Nかもしれませんが、そうでないこともあります。自明でない因数giが発見されたとき、Nがgi×(N/gi)に分解されたことになります。これの繰り返しをある程度継続することにより、いくつかの自明でない因数が発見され、結果としてNが分解されていくことが期待できます。(ただしcは0,-2以外の整数)を用いるのが普通です(註2)。これは乱数列ではありませんが、かなり乱数に近い振る舞いをすることが経験的に知られています。Nでの振る舞いが乱数に近いこと、また一方ではそれが確定的でもあること」、{xi}がこの両者を同時に満たすものであることがρ法の要です。上記アルゴリズムはあまりにも不可解に見えることでしょう。このようなまわりくどい手法が意味を持ち得るのは、偏に「Nの大きさには殆ど関係なく、素因数pの大きさにのみ依存した時間でpを発見し得る」という特性に依ります。p)が成り立つようなj,kがあったとします。N)を計算することでp(もしくはpを含むNの因数)を得ることができます。pについて考えてみます。その値は高々p個の値しかとり得ません。p)を満たすようなp+1以下の値j0,k0が存在することになります。p)なるものを用います。pで循環を始めます(この循環図の形がアルゴリズムの名前のもとになったものです)。このことにより、条件を満たすj,kは無数に存在しますので、その中で比較的計算しやすいものを探すわけです。p)なる(j,k)を探すといっても、実際にはpは未知ですので、合同式が成立するかどうかを判定することができません。合同式の成立を検出してからGCDを計算するのではなく、とにかく毎回GCDを計算してみる形を取ります。GCDが1だったときは合同式が不成立だったのだと考えて次の(j,k)の候補をあたることになります。...と、添え字(j,k)のあらゆるパターンの中を探していては効率が悪いです。そこで次の方法でこの問題を解決します。p}の循環周期です)。p)となることになります。d<(k0-j0)であり、k0≦p+1です。≦p+1であり、従ってj≦pです。このことにより、素因数pを発見するまでに必要な計算量がNの大きさよりはpの大きさに依存するというρ法の特性が導かれます。Nも満たしてしまう場合があります。pが循環する周期が等しい場合です。このとき、得られるGCDは全てNそのものとなってしまいますので、いつまで経ってもpを発見することはできません。ρ法による分解では、間違った答えを出すことはありませんが、答えが得られるとは限りません。実用上はかなりの確率で有効な答えが導かれることが知られています。答えが得られなくても、最初に用いたf(x)=x2+cとは異なるcを用いて再試行することで、多くの場合、答えを得ることができます。上に戻るRubyによる実装xiの値は途中でとても大きくなってしまい、計算コストが高くなります。必要なのはNとのGCDであって値そのものではないため、新たなxiの値を求める毎にNによる剰余だけを保存しておけば、値をN未満に抑えることができます。Nを使っても差し支えないわけです。Euclidの互除法でGCDを求める関数。引数から対象合成数を得る。x_1をランダムに決定。ループ回数の上限を(√n)+1にする。nにおけるcは、仮に1に固定してしまいました。必要ならば、分解しきれなかったときにcを変えて再試行するような処理を書き加えるべきでしょう。ubound上で議論したように、現在の乱数生成関数f(x)によって素因数pを発見可能ならば、それはp+1回ループした時点までに発見されます。素朴試し割り法のときに議論したように、√nまでの素因数が全て発見されれば、その時点で残っている因数もまた素因数です。従って、ループは(√n)+1回行なえば十分であると言えるでしょう。(他の小さな素因数の発見に失敗して、(√n)以上の大きな素因数plargeの分解にのみ、(√n)+1回目以降で成功するという可能性もないとは言いませんが、期待薄です)。n)をチェックしました。{xi}の項のうち、添え字が(i,2i)というパターンを満たすようなのペアに対してGCDをとっていたわけです。ここには無駄があります。y2=x4を計算する過程で必然的にx3も求めていますがこの計算結果は捨ててしまっており、gcd(y3-x3,n)を計算する段階に於いてx3を再計算しています。Brentは、(i,2i)というパターンを他のものに変更することを提案しました。...というものです。一般にiに対しi未満の最大の2のべきが対応するというパターンです。Brentの改良を取り入れれば、計算した値を無駄なく(しかも過剰でもなく)数列循環の検出に用いることができます。yの値は直前のxの値から流用できるため、独自に計算する必要はありません。関数div_while_divisibleの定義は省略。x_1をランダムに決定。"#{n}\n"一番上に戻る素朴試し割りとの組み合わせρ法の「確実に素因数を発見できるか分からない」という欠点を補うためには、予め素朴試し割り法を用いて、小さな素因数を全て取り除いておくことが有効です。試し割りの計算量とNの大きさを鑑みて、適当な上限naive_uboundを定め、それ以下の素因数は試し割りで処理することにします。これにより、次のような利点がもたらされます。2,3,5,...あたりの極めて小さな素因数がNに多数含まれる場合、これらがあちこちのGCDに分散して混入することを防止できます。GCDは素因子pを返すとは限らず、pを含むNの因数を返す可能性もあります。...などが返される可能性が高くなってしまいます。p,qがある程度大きな素因数の場合であれば、たまたまpqがGCDとして返ることはあっても、pq2はおそらくNを超えてしまうでしょう。極端に大きな次数を持つGCDが返る心配はないと言えます。s3が紛れ込んで収拾がつかなくなり兼ねません。素数判定が少し容易になります。得られたGCDがなお合成数である疑いがあるならば、そのGCDを再帰的に素因数分解する必要があります(これまでの実装では行なっていませんが)。素数であるかの判定にはある程度のコストが掛かります。naive_uboundまでの素因数が確実に取り除かれているならば、その後のρ法の適用で発見された(naive_ubound)の2乗以下の因数は全て素因数です。ある数Mが合成数ならば必ず√M以下の素因数を持つためです(素朴試し割り法のときの議論を参照してください)。大小比較のみならばコストは低いので、素数判定が少しだけ容易になります。関数div_while_divisibleの定義は省略。前節において小さな素因数は取り除いてしまうことにしました。pが成立してGCDが1以外になるのは稀である(周期k0-j0が長い)と言えます。そこで、毎回GCDを計算するのではなく何回かまとめてGCDをとることにします。何らかのrをとっておいて、どうせ大部分のy-xはNと互いに素であろうと考えて、次のようにするわけです。N)わざわざ積を計算するのは無駄に感じられる知れませんが、積の計算はGCDの計算に比べてかなり速いため、結局は時間短縮になります。y-xの積はそのまま保存しておく必要はありません。GCDをとるのに使うわけですから、掛けあわせる度にNによる剰余をとってそれを保存しておけば十分です。rの取り方rを必要以上に大きくとると、GCDをとる前に複数の素因子が出現してしまうかもしれません。すると、それら素因子の積しか得られないわけで、困ってしまいます。適切なrをとることが大切です。......といっても、具体的にどの程度にすべきかは難しい問題です。以下では、仮にr=10に固定したソースを示します。関数div_while_divisibleの定義は省略。