代数群因数分解アルゴリズム

代数群因数分解アルゴリズムは、 Nを法として定義される代数群において整数 Nを因数分解するアルゴリズムです。この群の構造は、未知の素因数p 1、p 2 、…を法として群の算術演算を定義する方程式を実行することによって得られる「被約群」の直和です。中国剰余定理により、 Nを法とする算術演算は、すべての被約群における算術演算に同時に対応します

目的は、Nを法として群の単位元ではないが、因数の1つを法として単位元となる元を見つけることです。そのため、このような片側単位元を認識する方法が必要です。一般的には、元を移動させ、被縮分群の単位元は変更しない操作を実行することで、このような片側単位元を見つけます。アルゴリズムが片側単位元を見つけると、それ以降の項もすべて片側単位元となるため、定期的に確認するだけで十分です。

アルゴリズム

計算は、 Nを法とする群の任意の元xを選び、その大きく滑らかな倍数Axを計算することによって進められます。少なくとも1つの被約群の位数がAの約数であるが、すべての被約群の位数がAの約数ではない場合、因数分解が得られます。元は複数の被約群において単位元である可能性があるため、素因数分解である必要はありません

一般的に、Aはある限界B 1未満のすべての素数の累乗の積としてとられ、Axはこれらの素数をxに連続的に乗じて計算されます。各乗算の後、または数回の乗算ごとに、片側単位元が成立するかどうかがチェックされます。（効率の低い単純なバージョンでは、限界B 1未満のすべての整数の積が使用されます。）[1]

2段階の手順

多くの場合、グループ元に複数の小さな整数を乗算する方が、それらの積よりも速く実行できます。これは通常、差に基づく方法です。つまり、連続する素数間の差を計算し、 を連続して加算します。これは、2段階の手順が合理的であることを意味します。まず、極限 B 1未満のすべての素数にxを乗じてAxを計算し、次にB 1とより大きな極限 B 2の間にあるすべての素数についてp Ax を調べます。これにより、グループの順序に対する滑らかさの要件が、 B 1べき乗滑らかであることから、 B 1と B 2の間の素数と B 1べき乗滑らかな数の積に緩和されます。 d i r {\displaystyle d_{i}r}

差分法は「第2段階」の基本的な手法である。モンゴメリの素数対法（1978）やブレント・スヤマ拡張などの修正法も存在する。[2]

より効率的な「ステージ2」の手法では、高速フーリエ変換を用いて実装された多項式乗算が用いられます。この手法は、1992年にモンゴメリーによってレンズトラのECM向けに初めて実証されましたが[3]、その後p -1およびp +1にも適用されました[2] 。

特定の代数群に対応する方法

実践的手法

代数群がNを法とする乗法群である場合、片側恒等式はNとの最大公約数を計算することによって認識され、結果はp  −1法です

代数群がNの二次拡大の乗法群である場合、結果はp  + 1 法であり、計算にはNを法とする数のペアが関係します。 Nの因数分解を知らずに、が実際に の二次拡大であるかどうかを判断することはできません。これには、 t がNを法とする平方剰余であるかどうかを知る必要がありますが、因数分解を知らずにこれを行う方法は知られていません。ただし、Nに非常に多くの因数がない場合は、最初に別の方法を使用する必要があります。ランダムにtを選択するか、t = A 2 − 4としてA を選択すること で、かなり早く二次の非剰余に遭遇します。t が平方剰余である場合、 p+1 法はp  − 1 法のより遅い形式に退化します。 Z / N Z [ t ] {\displaystyle \mathbb{Z} /N\mathbb{Z} [{\sqrt{t}}]} Z / N Z {\displaystyle \mathbb {Z} /N\mathbb {Z} }

代数群が楕円曲線である場合、楕円曲線の点の追加手順における反転の失敗によって片側恒等式が認識され、その結果が楕円曲線法となる。ハッセの定理によれば、 pを法とする楕円曲線上の点の数は、常にp以内である。 2 p {\displaystyle 2{\sqrt {p}}}

上記の代数群の3つはすべてGMP-ECMパッケージ[4]で使用されており、 2段階手順の効率的な実装と、標準的な2進指数計算アプローチよりも効率的なPRACグループ指数計算アルゴリズムの実装が含まれています。

その他の群

Nの高階拡大や、より高種数の代数曲線に対応する群など、他の代数群の使用が時折提案されますが、ほとんどの場合、非現実的です。例えば、効率的な群法を持つ超楕円曲線のヤコビ多様体を使用することができます。これらの手法は、あるd > 1に対してp dの位数の数に滑らかさの制約をもたらし、 p の位数の数よりも滑らかである可能性がはるかに低くなります

実用的な考慮事項

計算量

単純な第1段階ではビット演算を使用し、素数累乗のみの第1段階では を使用します。ここで、Nは因数分解される数であり、 2つのxビット整数を乗算するコストを表します（実際にはFFTベースの方法を使用）。[1] O （ B 1 ログ ⁡ （ B 1 ) M （ ログ ⁡ （ N ) ) ) {\displaystyle O(B_{1}\log(B_{1})M(\log(N)))} O （ B 1 M （ ログ ⁡ （ N ) ) ) {\displaystyle O(B_{1}M(\log(N)))} M （ × ) {\displaystyle M(x)} M （ ログ ⁡ （ N ) ) ＝ O （ N ログ ⁡ （ N ) ログ ⁡ ログ ⁡ （ N ) ) {\displaystyle M(\log(N))=O(N\log(N)\log\log(N))}

標準的な（差分ベースの）第2段階では、ビット演算が用いられる。[1]多項式ベースの第2段階では、ビット演算が用いられる（と仮定すれば、項は無視できるが、これはよくあるケースである）。畳み込みのサイズを変えることで、メモリと空間のトレードオフが生じる。メモリ使用量が2倍になるごとに、同じ計算量で の進歩も2倍になる。[2] O （ （ B 2 − B 1 ) M （ ログ ⁡ （ N ) ) ) {\displaystyle O((B_{2}-B_{1})M(\log(N)))} O ( B 2 − B 1 log ⁡ ( B 2 − B 1 ) M ( log ⁡ ( N ) ) ) {\displaystyle O({\sqrt {B_{2}-B_{1}}}\log(B_{2}-B_{1})M(\log(N)))} B 1 {\displaystyle B_{1}} B 2 >> B 1 {\displaystyle B_{2}>>B_{1}} B 2 {\displaystyle B_{2}}

成功確率

Kruppa (2010) セクション5.3および5.4を参照。[5]

参照

参考文献

  1. ^ abc Galbraith, Steven (2012). 「代数群を用いた素数判定と整数因数分解」公開鍵暗号の数学(PDF) . ケンブリッジ大学出版局. pp.  261– 268. 2025年8月16日閲覧
  2. ^ abc Montgomery, Peter L.; Kruppa, Alexander (2008). 「改良されたステージ2からP±1因数分解アルゴリズム」(PDF) .アルゴリズム的数論. 5011 : 180–195 . doi :10.1007/978-3-540-79456-1_12.
  3. ^ ポール・ツィンマーマン、ブルース・ドッドソン (2006). 「ECMの20年」(PDF) .アルゴリズム数論. 4076 : 525–542 . doi :10.1007/11792086_37.HAL
  4. ^ 「ZIMMERMANN Paul/ecm (GMP-ECM)」. gitlab.inria.fr
  5. ^ Kruppa, Alexander (2010). 整数乗算と因数分解の高速化(PDF) (博士論文). アンリ・ポアンカレ大学.– 本稿では、クルッパがGMP-ECMやその他の因数分解プログラムに寄与したアルゴリズムについて解説しています。一部の章は既に他の文献で発表されています。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algebraic-group_factorisation_algorithm&oldid=1325136021"