NumberTheory`FactorIntegerECM`

このパッケージはレンストラ(Lenstra)の楕円曲線法の因数分解を実装する．パッケージは約18桁までの素因数を比較的短時間（ワークステーションで最大3時間）で求めるように設計されている．これはMathematica の整数の因数分解を，40桁以下のすべての数に拡張するパッケージである．このパッケージのプログラムは「Speeding up the Pollard and Elliptic Curve Methods of Factorization」（P. L. Montgomery著，Mathematics of Computation 48，1987）の243-264ページで述べられているアルゴリズムほぼそのままの実装である．

FactorIntegerECMの使用

このアルゴリズムは1つの因数を返す．これは必ずしも素数ではない．完全な因数分解を得るためには，因数と余因数にFactorIntegerECMまたは組込み関数のFactorIntegerを適用しなければならない．アルゴリズムは確率的なものであるので，同じような入力をした場合でも，実行時間に差が生じることがある．このアルゴリズムでは擬似乱数の生成にSeedRandom[101]が使われるので，プログラムは同じ入力については毎回同じ動作をする．

FactorIntegerECMは組込み関数PrimeQおよびFactorIntegerの拡張として用いられなければならない．このアルゴリズムは入力が素数の場合は必ず失敗する．FactorIntegerECMの入力に素数を渡してはならない．FactorIntegerECMを使用する前に，その数が素数でないかどうかをPrimeQを使って確かめなければならない．

このアルゴリズムは，与えられた数がFactorIntegerで因数分解されていないため，その最小の素因数が少なくともであるという仮定の元に設計されている．アルゴリズムは桁以下の因数を求めるように最適化されているため，桁以下のほとんどの数を因数分解することができる（このような数は，因数分解が難しいときは素因数が2つだけであることが多い）．

パッケージをロードする．

In[1]:= <<NumberTheory`FactorIntegerECM`

FactorIntegerECMは因数を1つだけ返す．

In[2]:= FactorIntegerECM[91]

Out[2]=

一般に，指定の範囲で因数分解が最も難しい数は，ほぼ同じ大きさの2つの異なる因数を持つ数である．このような数は，組込み関数Primeを用いて生成できる．

In[3]:= Prime[10^7] Prime[10^7+1]

Out[3]=

これを因数分解する．

In[4]:= FactorIntegerECM[%]

Out[4]=

次はかなり大きな整数である．

In[5]:= (2^58 - 27) * (2^127 - 1)

Out[5]=

FactorIntegerを使って因数分解を行うより，次のように計算する方がはるかに速く計算できる．

In[6]:= FactorIntegerECM[%]

Out[6]= 288230376151711717

ECM法はH. W. レンストラによって発見され，解析された．この方法は1985年2月14日に初めて「Elliptic Curve Factorization」で案内され，1987年にH. W. レンストラ著「Factoring Integers with Elliptic Curves」(Annals of Mathematics 126)で出版された．

この方法はJ. ポラード(Pollard)の因数分解アルゴリズムを一般化したもので，ランダムな楕円曲線上のランダムな点を生成して合成数を因数分解し， がを計算するために代数的な群構造を持っているということを利用する．ここではアルゴリズムの途中で選ばれた比較的小さな整数である．が群（はの素因数）上で単位元なら，は因数分解できる（は約されるであると考える必要がある）．この場合，無効な逆元が発生する（つまり無効なPowerMod[a, -1, n]の使用が起る）ので，アルゴリズムで検出できる．これはグループ（はの素因子）の位数が未満の素数でのみ割り切れるときに必ず起る．これは，さまざまな曲線を選ぶことができ，が変化するに従ってがの周りに分布するため，妥当な時間で起る．つまり，最終的には小さな素数でのみ割り切れる値に到達するということである（ここで，はの固定の素因子である）．

レンストラの元のアルゴリズムはほぼ理論的な興味によるものである．実装の考えの多くはモンゴメリ(Montgomery)の論文に由来している．法の改良案として最初にポラードにより提唱された最も重要な点は，このアルゴリズムに第2段階を導入するということである．これは小さな因数を持つ数だけを探すのでなく，大きな1つの因数以外の小さな因数すべてを持つ数を探すという案である．従ってアルゴリズムの第2段階は第1段階で計算された点を取り，のいずれかがの因数分解を生成しているかどうかを見るというものである．ここではと（このプログラムでは）の間にある素数である．この第2段階は，本質的に重要な改善点である．

モンゴメリらは上述のものを効率的に実装するさまざまな方法を発見した．このパッケージのプログラムはこれらの考え方のうちのいくつかが反映されている．このことについての導入として「Factorization and Primality Testing」（D. Bressoud著，Springer-Verlag出版，1989）が役立つだろう．

このアルゴリズムは非常に複雑であるため，小さい因数を持つ数にこれを用いるのは効率的ではない．このような因数は試し除算など他の方法を用いた方がより効率的である．そのため，関数FactorIntegerECM[n]はの完全な因数分解は行わず，因数を1つだけ返す．

従ってこのパッケージは，パッケージNumberTheory`NumberTheoryFunctions`に含まれるSquareFreeQと同様に，FactorIntegerで直接因数分解できない因数を見付ける方法として，または因数が1度に1つだけ必要な場合に使われるべきである．

FactorIntegerECMのオプション

FactorIntegerECMのオプションを使うと，アルゴリズムのパラメータの値を変化させたり，アルゴリズムの全ステップ数を制限したりすることができる．これを用いると，完全に因数分解を行わなくても，小さな因数について大きな数を検索することができる．

オプションFactorSizeは探している因数の大きさを指定するものである．一般的な目的で因数分解を行う場合は，通常数のどの因数でも構わないだろう．そのため，デフォルトのFactorSizeの値は約である．

このアルゴリズムは入力の大きさに応じて，多くの曲線を同時に用いる．オプションCurveNumberを使うと，同時にいくつの曲線を使うかが指定できる．このオプションの値は2のベキ乗でなければならない．CurveNumberのデフォルトの値は指定の数nの大きさによる．の場合は，の場合は，の場合はである．

より多くの曲線を同時に使うことの利点に，アルゴリズムの第1段階では使用するGCDが減少し，第2段階で解釈オーバーヘッドが減るということがある．一方で，ある曲線で求められた重要でない因数が，このアルゴリズムがすべての曲線について計算を終えるまで待っていなければならないという欠点もある．従って，曲線の数は全体としてどれだけの曲線が必要かに依存する．

オプションCurveCountLimitはこのアルゴリズムで使用する曲線の数の上限を指定するものである．これを用いると，ユーザは因数が見付かる前にアルゴリズムを終了させることができる．デフォルトの曲線の数はである．これは本質的には無限数である．

このプログラムに必要なメモリ量はそれほど多くはない．個の素数の表と個の2進数の表が設定できる．