合理的なふるい

Integer factorization algorithm

数学において、有理数体ふるいは整数を素因数に分解する一般的なアルゴリズムです。これは一般数体ふるいの特殊なケースです。一般アルゴリズムよりも効率は劣りますが、概念的にはより単純です。これは、一般数体ふるいの仕組みを理解するための有用な第一歩となります。

方法

合成数 $n$ を因数分解しようとするとしよう。境界値 $B$ を選び、因数基数 $（これをP$ と呼ぶ）を特定する。これは $B$ 以下のすべての素数の集合である。次に、 $z$ と $z$ $+$ $nが$ $B$ -滑らかであるような正の整数 $z$ を探す。つまり、それらの素因数はすべて $Pに含まれる。したがって、適切な指数$ $a$ $i$ と $b$ $i$ について、次のように書ける。

$z=\prod _{p_{i}\in P}p_{i}^{a_{i}}\qquad {\text{and}}\qquad z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}.$

しかし、 $z$ とnは $nを$ 法として合同であり、したがって、私たちが見つけた整数 $zのそれぞれは、$ $P$ の要素間の乗法関係（mod $n$ ）を生み出します。つまり、 $z+n$

\prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}

（ここで、 $ai$ $と$ b $i は$ 非負の整数です。）

これらの関係を十分に生成したら（一般に、関係の数は $P$ のサイズより少し多くなれば十分です）、線形代数の方法を使用して、素数の指数がすべて偶数になるようにこれらのさまざまな関係を掛け合わせることができます。これにより、 $a$ $2$ $\equiv$ $b$ $2$ $(mod$ $n$ $)$ の形式の平方の合同が得られ、これは $n$ $= gcd($ $a$ $+$ $b$ $,$ $n$ $) \times gcd($ $a$ $-$ $b$ $,$ $n$ $)$ の因数分解に変換できます。この因数分解は自明である（つまり、 $n$ $=$ $n$ $\times 1$ ）と判明する可能性があり、その場合は関係の異なる組み合わせで再試行する必要がありますが、運が良ければ $n$ の因数の非自明なペアが得られ、アルゴリズムは終了します。

例

有理ふるいを用いて整数 $n = 187 を因数分解します。任意の値$ $B = 7$ を試し、因数分解の底 $P = {2,3,5,7}$ を得ます。最初のステップは、 $n が$ $P$ の各要素で割り切れるかどうかをテストすることです。明らかに、 $n が$ これらの素数のいずれかで割り切れる場合は、これで完了です。しかし、187 は 2、3、5、7 では割り切れません。次に、 $z$ の適切な値を探します。最初のいくつかは 2、5、9、56 です。これら 4 つの $z$ の適切な値から、4 つの乗法関係式（mod 187）が得られます。

2^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0}3^{3}5^{0}7^{1}

1

2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6}3^{1}5^{0}7^{0}

2

2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2}3^{0}5^{0}7^{2}

3

2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0}3^{5}5^{0}7^{0}

4

これらを組み合わせて偶数指数を得るには、本質的に異なる方法がいくつかあります。例えば、

( 1 )×( 4 ): これらを掛け合わせ、7の共通因数を消去すると（7は $P$ $の元数であり、 n$ と互いに素であることが既に判明しているので^{[1] ）、} $24 \equiv 3 8 (mod n)$ となる。結果として得られる因数分解は $187 = gcd(3 4 + 2 2, 187) \times gcd(3 4 - 2 2, 187) = 11 \times 17となる$ 。

あるいは、式（３）はすでに適切な形になっている。

( 3 ): これは $32 \equiv 14 2 (mod n)$ を意味し、因数分解は $187 = gcd(14 + 3, 187) \times gcd(14 - 3, 187) = 11 \times 17と$ なります。

アルゴリズムの限界

$一般数体ふるいと同様に、有理ふるいはp m$ （ $p$ は素数、 $m$ は整数）の形の数を因数分解することができません。しかし、これは大きな問題ではありません。そのような数は統計的に稀であり、さらに、与えられた数がこの形であるかどうかを確認する簡単で高速な方法があります。おそらく最もエレガントな方法は、任意の $1 < b \leq log$ $2$ $($ $n$ $)$ に対して $⌊ n 1/ b ⌋ b = n$ が成り立つかどうかを、ニュートン法の整数版を用いて確認することです。^[2]

$最大の問題は、 z$ と $z$ $+$ $nの$ 両方が $B$ 滑らかになるような十分な数の $z$ を見つけることです。任意の $Bに対して、$ $B$ 滑らかな数の割合は数の大きさとともに急速に減少します。そのため、 $n$ が大きい場合（例えば100桁）、アルゴリズムが機能するのに十分な $数のz$ を見つけることは困難、あるいは不可能になります。一般数体ふるいの利点は、ここで要求されている $n$ 次の滑らかな数ではなく、 $exp($ $C$ $(log($ $n$ $))$ $2/3$ $(log(log($ $n$ $)))$ $1/3$ $)$ の滑らかな数 $（C$ $> 0$ ）を検索するだけで済むことです。^[3]

参考文献

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. [2] から入手可能。
AK Lenstra、HW Lenstra、Jr.（編）数体ふるいの開発、数学講義ノート1554、Springer-Verlag、ニューヨーク、1993年。

脚注

^ 一般に共通因数は合同式で相殺することはできませんが、この場合は相殺することができます。これは、前述のように、因数底の素数はすべてnと互いに素である必要があるためです。モジュラー逆数を参照してください。
^ R. CrandallとJ. Papadopoulos、「AKSクラスの素数判定の実装について」 [1]から入手可能
^ AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), p. 328

[1] 一般に共通因数は合同式で相殺することはできませんが、この場合は相殺することができます。これは、前述のように、因数底の素数はすべてnと互いに素である必要があるためです。モジュラー逆数を参照してください。

[2] R. CrandallとJ. Papadopoulos、「AKSクラスの素数判定の実装について」 [1]から入手可能

[3] AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), p. 328