ディクソンの因数分解法

数論において、ディクソン因数分解法（ディクソンのランダムスクエア法^[1]またはディクソンアルゴリズムとも呼ばれる）は、汎用的な整数因数分解 アルゴリズムであり、典型的な因数基底法である。他の因数基底法とは異なり、その実行時限界は、多項式が取る値の滑らかさに関する推測に依存しない厳密な証明を伴う。

このアルゴリズムはカールトン大学の数学者ジョン・D・ディクソンによって設計され、1981年に発表されました。^[2]

基本的な考え方

ディクソン法は、因数分解しようとする整数Nを法とする平方数の合同性を求めることを基本としています。フェルマー因数分解法は、ランダムまたは擬似ランダムな x値を選択し、整数x ²  mod Nが（整数において） 完全な平方数となることを期待することで、このような合同性を求めます。

${\displaystyle x^{2}\equiv y^{2}\quad ({\hbox{mod }}N),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}N).}$

例えば、N = 84923の場合（ √ Nより大きい最初の数である 292 から始めて数えていくと） 、 505 ² mod 84923は 256 となり、これは 16 の平方です。つまり、(505 − 16)(505 + 16) = 0 mod 84923 となります。ユークリッドの法則を用いて505 − 16とNの最大公約数を計算すると 163 となり、これはNの因数です。

実際には、ランダムなx値を選択すると、 Nより小さい正方形は√ N個しかないため、正方形の合同を見つけるのに非現実的な長い時間がかかります。

ディクソン法では、「整数の平方である」という条件を、「小さな素因数のみを持つ」というはるかに弱い条件に置き換えます。たとえば、84923 より小さい平方数は 292 個あります。84923 より小さい数で素因数が 2、3、5、または 7 のみである数は 662 個あります。また、素因数がすべて 30 未満の数は 4767 個あります。(このような数は、ある境界Bに関してB 滑らかと呼ばれます。)

固定された小さな素数集合に対して、平方を因数分解できる数が多数ある場合、行列の 2 を法とする線型代数は、平方が偶数乗の小さな素数の積に結合される のサブセット、つまり、平方が N を法とする (できれば異なる) 数の平方に掛けられる のサブセットを与えます。${\displaystyle a_{1}\ldots a_{n}}$ ${\displaystyle a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}}$ ${\displaystyle b_{1}\ldots b_{m}}$ ${\displaystyle e_{ij}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$

方法

合成数Nを因数分解するとする。境界値Bを選び、因数分解の基数（これをPと呼ぶ）を特定する。これはB以下のすべての素数の集合である。次に、 z ²  mod  NがB -滑らかとなるような正の整数zを求める。したがって、適切な指数a _iに対して、 次のように書ける。

${\displaystyle z^{2}{\text{ mod }}N=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

これらの関係が十分に生成されたら（関係の数は一般にPのサイズより少し多くなれば十分です）、ガウス消去法などの線形代数の方法を使用して、右側の素数の指数がすべて偶数になるようにこれらのさまざまな関係を乗算できます。

${\displaystyle {z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{where }}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod {2}})}}$

これにより、a ² ≡ b ² (mod N )という形式の平方合同が得られ、これはNの因数分解、N = gcd ( a + b , N ) × ( N /gcd( a + b , N )に変換できます。この因数分解は、a ≡ ± b (mod N )の場合にのみ発生する、つまりN = N × 1となる可能性があります。その場合は、関係の異なる組み合わせで再度試行する必要があります。ただし、Nの因数のペアが自明でない場合、アルゴリズムは終了します。

擬似コード

このセクションは Dixon (1981) から直接引用したものです。

ディクソンのアルゴリズム

初期化。Lを範囲[1, n ]の整数のリストとし、P = { p ₁ , ..., p _{h }を}h個の素数≤ vのリストとする。BとZは初期状態では空のリストとする（ZはBによってインデックス付けされる）。

ステップ1. Lが空の場合、終了（アルゴリズム失敗）。そうでない場合、 Lの最初の項zを取り、それをLから削除し、ステップ2に進む。

ステップ2. z ² mod nの最小の正の剰余としてwを計算します。wを次のように因数分解します。

${\displaystyle w=w'\prod _{i}p_{i}^{a_{i}}}$

ここで、w ′ はPに因子を持たない。w ′ = 1の場合はステップ3へ進み、それ以外の場合はステップ1に戻る。

ステップ3. a ← ( a ₁ , ..., a _h )とする。aをBに、zをZに追加する。Bの要素数が最大でhであればステップ1に戻る。そうでない場合はステップ4に進む。

ステップ4. B内の最初のベクトルc のうち、B内の以前のベクトルに線形従属（mod 2）するベクトル c を見つけます。BとZ からcを削除します。次の係数を計算します。 ${\displaystyle z_{c}}$ ${\displaystyle f_{b}}$

${\displaystyle \mathbf {c} \equiv \sum _{b\in B}f_{b}\mathbf {b} {\pmod {2}}}$

定義する：

${\displaystyle \mathbf {d} =(d_{1},\dots ,d_{n})\gets {\frac {1}{2}}\left(\mathbf {c} +\sum f_{b}\mathbf {b} \right)}$

ステップ5に進みます。

ステップ5.計算:

${\displaystyle x\gets z_{c}\prod _{b}z_{b}^{f_{b}},\quad y\gets \prod _{i}p_{i}^{d_{i}}}$

となることによって：

${\displaystyle x^{2}\equiv \prod _{i}p_{i}^{2d_{i}}=y^{2}\mod n.}$

またはの場合は、ステップ 1 に戻ります。それ以外の場合は、以下を返します。 ${\displaystyle x\equiv y}$ ${\displaystyle x\equiv -y{\pmod {n}}}$

${\displaystyle \gcd(n,x+y)}$

これはnの非自明な因数を提供し、正常に終了します。

ステップバイステップの例:因数分解(n= 84923）ディクソンのアルゴリズムを使用して

この例はLeetArxivサブスタックから直接引用したものです。^[3]オリジナルの著者にクレジットが与えられています。

• 初期化:
  • 1から84923までの範囲の数値のリストLを定義します。

${\displaystyle L=\{1,\dots ,84923\}}$

• 平滑化係数である値vを定義します。

${\displaystyle v=7}$

• v以下の素数をすべて含むリストPを定義します。

${\displaystyle P={2,3,5,7}}$

• 2つの空リストBとZを定義します。Bはべき乗のリスト、Zは整数のリストです。

${\displaystyle B=[]}$

${\displaystyle Z=[]}$

• ステップ1：値の 反復${\displaystyle z}$
  • リスト をインデックスする for ループを記述します。 の各要素はとしてインデックス付けされます。 for ループはリストの最後で終了します。${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle z}$

int n = 84923 ; for ( int i = 1 ; i <= n ; i ++ ) { int z = i ; }   
        

       

• ステップ2：V滑らかな素因数分解の 計算${\displaystyle z^{2}\mod n}$
  • 続行するには、各zについて計算し、結果を素因数分解として表現します。${\displaystyle z^{2}\mod 84923}$

${\displaystyle 1^{2}\mod 84923\equiv 1\mod 84923=2^{0}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0}\mod 84923}$

${\displaystyle \vdots }$

${\displaystyle 513^{2}\mod 84923=8400\mod 84923=2^{4}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}\mod 84923}$

${\displaystyle \vdots }$

${\displaystyle 537^{2}\mod 84923=33600\mod 84923=2^{6}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}\mod 84923}$

${\displaystyle 538^{2}\mod 84923=34675\mod 84923=5^{2}\cdot 19^{1}\cdot 73^{1}\mod 84923}$

このステップは、範囲内のすべてのz値に対して続行されます。

• ステップ 3 :が7 滑らかな場合は、その累乗をリストに追加し、リストに追加します。${\displaystyle z^{2}\mod 84923}$ ${\displaystyle B}$ ${\displaystyle z}$ ${\displaystyle Z}$

${\displaystyle Z=\{1,513,537\}}$

${\displaystyle B=\{[0,0,0,0],[4,1,2,1],[6,1,2,1]\}}$

• ステップ 4 : このステップは 2 つの部分に分かれています。

パート 1 : 2 を法とする数を求めます。${\displaystyle B}$

${\displaystyle B={\begin{pmatrix}0&0&0&0\\4&1&2&1\\6&1&2&1\end{pmatrix}}\mod 2\equiv B={\begin{pmatrix}0&0&0&0\\0&1&0&1\\0&1&0&1\end{pmatrix}}}$

パート2 ： 合計が偶数になる行の組み合わせがあるかどうかを確認する${\displaystyle B}$

たとえば、Rowと Rowを合計すると、偶数のベクトルが得られます。${\displaystyle 2}$ ${\displaystyle 3}$

${\displaystyle R_{2}=\{0,1,0,1\}}$ そして${\displaystyle R_{3}=\{0,1,0,1\}}$

それから

${\displaystyle R_{2}+R_{3}=\{0,1,0,1\}+\{0,1,0,1\}}$

${\displaystyle R_{2}+R_{3}=\{0,2,0,2\}}$ 。

• ステップ 5  : このステップは 4 つの部分に分かれています。
  • パート1（xの求め方）：ステップ4で求めた行の対応する値を掛け合わせます。そして平方根を求めます。これでxが得られます。 ${\displaystyle z}$ ${\displaystyle x}$
    • 2 行目では、 がありました。${\displaystyle 2^{4}*3^{1}*5^{2}*7^{1}}$
    • 3 行目では、 がありました。${\displaystyle 2^{6}*3^{1}*5^{2}*7^{1}}$
    • したがって、次のことがわかります 。${\displaystyle x}$

${\displaystyle {\begin{array}{ll}(513\cdot 537)^{2}\mod 84923=y^{2}\\\\{\text{where}}\quad x^{2}\mod 84923=(513\cdot 537)^{2}\mod 84923\\\\{\text{thus}}\quad x=(513\cdot 537)\mod 84923\\\\{\text{so}}\quad x=275481\mod 84923\\\\{\text{Finally}}\quad x=20712\mod 84923\\\end{array}}}$

• パート2（yの求め方） ：ステップ4で求めた行に対応する滑らかな因数分解を掛け合わせます。そして平方根を求めます。これで となります。${\displaystyle y}$

${\displaystyle {\begin{array}{ll}y^{2}=(2^{4}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1})\times (2^{6}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1})\\\\{\text{By the multiplication law of exponents,}}\\y^{2}=2^{(4+6)}\cdot 3^{(1+1)}\cdot 5^{(2+2)}\cdot 7^{(1+1)}\\\\{\text{Thus,}}\\y^{2}=2^{10}\cdot 3^{2}\cdot 5^{4}\cdot 7^{2}\\\\{\text{Taking square roots on both sides gives}}\\y=2^{5}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}\\\\{\text{Therefore,}}\\y=32\times 3\times 25\times 7\\\\{\text{Finally,}}\\y=16800\end{array}}}$

• パート3. (x + yとx - yを求めます)ここで、x = 20712、y = 16800です。

${\displaystyle x+y=20712+16800=37512}$

${\displaystyle x-y=20712-16800=3912}$

• パート4. GCD(x+y, n)とGCD(xy, n)を計算します。ここで、 n = 84923、x+y = 292281、xy = 258681です。

${\displaystyle {\begin{array}{ll}\gcd(37512,84923)=521\\\gcd(3912,84923)=163\end{array}}}$

クイックチェックでは が表示されます。 ${\displaystyle 84923=521\times 163}$

最適化

二次ふるい法はディクソン法の最適化です。Nの平方根に近いxの値を選択し、 Nを法とするx ²が小さくなるようにすることで、滑らかな数を得る可能性を大幅に高めます。

ディクソン法を最適化する他の方法としては、行列方程式を解くためのより優れたアルゴリズムを用いることが挙げられます。これは、行列の疎性を利用するものです。数zは 個以上の因数を持てないため、行列の各行はほぼすべてゼロになります。実際には、ブロックランチョス法がよく用いられます。また、因数基数の大きさは慎重に選択する必要があります。小さすぎると、その上で完全に因数分解できる数を見つけるのが難しくなり、大きすぎると、より多くの関係式を収集する必要が生じます。 ${\displaystyle \log _{2}z}$

より洗練された分析では、ある数の素因数がすべて より小さい確率で程度になるという近似 (ディックマン・ド・ブリュイン関数の近似) を使用すると、因数基数が小さすぎると大きすぎる場合よりもはるかに悪い結果になり、理想的な因数基数のサイズは のべき乗であることが示されます。 ${\displaystyle N^{1/a}}$ ${\displaystyle a^{-a}}$ ${\displaystyle \exp \left({\sqrt {\log N\log \log N}}\right)}$

ディクソン法の最適な複雑さは

${\displaystyle O\left(\exp \left(2{\sqrt {2}}{\sqrt {\log n\log \log n}}\right)\right)}$

ビッグO記法では、または

${\displaystyle L_{n}[1/2,2{\sqrt {2}}]}$

L表記法で。

参考文献

1. Kleinjung, Thorsten; et al. (2010). 「768ビットRSA係数の因数分解」. Advances in Cryptology – CRYPTO 2010 . Lecture Notes in Computer Science. Vol. 6223. pp.  333– 350. doi :10.1007/978-3-642-14623-7_18. ISBN 978-3-642-14622-0. S2CID  11556080。
2. Dixon, JD (1981). 「整数の漸近的高速因数分解」(PDF) . Math. Comp. 36 (153): 255– 260. doi : 10.1090/S0025-5718-1981-0595059-1 . JSTOR  2007743.
3. Kibicho, Murage (2025). 手書きの論文実装: 漸近的に高速な整数の因数分解.