ファクターベース

計算数論において、因数基数は、与えられた整数の潜在的な因数を 広範囲にふるい分けるアルゴリズムの数学的ツールとして一般的に使用される素数の小さな集合です。

因数分解アルゴリズムでの使用

因数基底とは、比較的小さな異なる素数Pの集合であり、時には −1 も含まれる。^[1]整数nを因数分解したいとする。何らかの方法で、、、が選択された因数基底上で完全に因数分解できる、つまりそれらの素因数がすべてPに含まれるような整数ペア ( x , y )を多数生成する。 ${\displaystyle x\neq \pm y}$ ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$ ${\displaystyle x^{2}{\pmod {n}}{\text{ と }}y^{2}{\pmod {n}}}$

実際には、すべての素因数があらかじめ選択された因数基数に含まれるような整数xがいくつか見つかる。各式を、因数基数における因数の指数を整数要素とする行列のベクトルとして表す。行の線形結合は、これらの式の乗算に対応する。行間の2を法とする線形依存関係により、望ましい合同が導かれる。^[2]これにより、本質的には問題が線形方程式のシステムへと再定式化され、ガウス消去法などのさまざまな方法を使用して解くことができる。実際には、システムの特定の特性を利用する ブロックLanczosアルゴリズムなどの高度な方法が使用されます。${\displaystyle x^{2}{\pmod {n}}}$ ${\displaystyle x^{2}{\pmod {n}}}$ ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$

この合同式は自明な を生成する可能性があります。この場合、別の適切な合同式を見つけようとします。因数分解を繰り返してもうまくいかない場合は、異なる因数分解基数を使って再試行できます。 ${\displaystyle \textstyle n=1\cdot n}$

アルゴリズム

因数基底は、例えばディクソン因数分解、二次ふるい、数体ふるいなどで用いられます。これらのアルゴリズムの違いは、本質的には( x , y )候補を生成する手法にあります。因数基底は、離散対数を計算する指数計算アルゴリズムでも用いられます。^[3]

参考文献

1. コブリッツ、ニール（1987年）、数論と暗号学講座、シュプリンガー・フェアラーク、p.133、ISBN 0-387-96576-9
2. トラップ、ウェイド; ワシントン、ローレンス C. (2006)、『暗号理論入門（第2版）』、プレンティス・ホール、185ページ、ISBN 978-0-13-186239-5
3. スティンソン、ダグラス・R.（1995年）、暗号/理論と実践、CRCプレス、p.171、ISBN 0-8493-8521-0