プログラミング/多倍長整数/ショーンハーゲ・ストラッセン法 (NTT版)

ショーンハーゲ・ストラッセン法は、非常に大きな数同士の掛け算を効率的に計算するためのアルゴリズムです。[[../カラツバ法|カラツバ法]]や[[../Toom-Cook乗算|Toom-Cook法]]をさらに発展させたもので、より大きな数の掛け算に対して効果的です。 このアルゴリズムは、数を多項式として表現し、数論変換（NTT: Number Theoretic Transform）を利用することで、掛け算の計算量を大幅に減らすことができます。

通常の掛け算との違い

通常の掛け算では、$n$桁の数同士を掛けると、$O(n^2)$の計算量が必要です。 一方、ショーンハーゲ・ストラッセン法では、理論的に$O(n\log n\log \log n)$の計算量で掛け算を行うことができます。

NTTを用いたショーンハーゲ・ストラッセン法

ショーンハーゲ・ストラッセン法の基本的な手順は以下の通りです：

1. 掛け算する大きな数を多項式として表現する
2. その多項式をNTTを用いて変換する
3. 変換された値同士を掛け合わせる
4. 逆NTTを用いて、結果の多項式を復元する
5. 復元した多項式から、最終的な掛け算の結果を求める

NTTとFFTの違い

従来のショーンハーゲ・ストラッセン法ではFFT（高速フーリエ変換）を使用していましたが、本バージョンではNTTを使用します。NTTはFFTの整数版と考えることができ、以下の利点があります：

1. 複素数の代わりに整数のみを使用するため、丸め誤差がない
2. モジュラ演算を使用するため、オーバーフローの心配が少ない
3. 特定の条件下では、FFTよりも高速に計算できる

多項式表現と原始根

例えば、大きな数 $A$ を次のように多項式として表現します：

$A=a_0+a_{1}x+a_2{x}^2+\cdots +a_{n-1}{x}^{n-1}$

NTTでは、素数 $p$ を法とする $n$ 次の原始根 $g$ を使用します：

$g^n\equiv 1(\mathrm{mod}p)$ かつ$g^k\equiv ̸1(\mathrm{mod}p)$ （$k<n$のとき）

NTTの実行

NTTは以下の手順で実行されます：

1. 多項式 $A(x)$ の係数を $a_i$ とする
2. $y_k=\sum _{i=0}^{n-1}{a}_i{g}^{ik}modp$ を計算する（$k=0,1,\dots ,n-1$）
3. $y_k$ が変換後の値となる

逆NTTも同様の手順で、$g$ の代わりに $g^{-1}$ を使用します。

なぜ効率的か

NTTを用いたショーンハーゲ・ストラッセン法が効率的な理由は以下の通りです：

1. NTTとその逆変換を高速に計算できる（FFTと同様の原理）
2. 変換後の掛け算は単純なモジュラ乗算になる
3. 整数演算のみを使用するため、高精度な結果が得られる

実用上の注意点

NTTを使用する場合、適切な素数 $p$ を選ぶ必要があります。一般的に、$p=c\cdot 2^k+1$ の形（$c$ は小さな奇数）の素数が使われます。これは、2の冪乗の周期を持つ原始根が存在し、計算を効率化できるためです。

まとめ

ショーンハーゲ・ストラッセン法にNTTを適用することで、高精度かつ高速な大数の掛け算が可能になります。この方法は、現代の暗号技術や精度の高い数値計算など、様々な分野で重要な役割を果たしています。