シェーンハーゲ・シュトラッセンアルゴリズム

${\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}}$、 どこ${\displaystyle N(n)=2^{n}+1}$。

許可することで：

${\displaystyle a_{i}'=\theta ^{i}a_{i}}$そして${\displaystyle b_{j}'=\theta ^{j}b_{j},}$

どこ$\displaystyle \theta ^{N}=-1}$n 乗根であることから、^次のことがわかる。^{[ 8 ]}

${\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}$

つまり、重さを使うことができる$\displaystyle \theta ^{i}}$、そして、$\displaystyle \theta ^{-k}}$後。

重量の代わりに、$\displaystyle \theta ^{N}=-1}$再帰の最初のステップで（${\displaystyle n=N}$) 計算すると次のようになります。

${\displaystyle C_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(N)}}}=\sum _{(i,j):i+j=k}a_{i}b_{j}-\sum _{(i,j):i+j=k+n}a_{i}b_{j}}$

複素数を扱う通常のFFTでは、以下を使用します。

$${\displaystyle \exp \left({\frac {2k\pi i}{n}}\right)=\cos {\frac {2k\pi }{n}}+i\sin {\frac {2k\pi }{n}},\qquad k=0,1,\dots ,n-1.}$$

${\displaystyle {\begin{aligned}C_{k}&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=e^{-i2\pi k/n}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}e^{i2\pi k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}$

しかし、FFTはシェーンハーゲ・シュトラッセンにおけるNTT（数論的変換）としても使用できます。これは、有限体（例えば）で数を生成するためにθを使用する必要があることを意味します。${\displaystyle \mathrm {GF} (2^{n}+1)}$)

有限体GF( r )における1の根とは、次の条件を満たす要素 a のことである。${\displaystyle \theta ^{r-1}\equiv 1}$または${\displaystyle \theta ^{r}\equiv \theta }$例えば、pが素数である場合、 GF( p ) は次のようになります。${\displaystyle \{1,2,\ldots ,p-1\}}$。

注目してください${\displaystyle 2^{n}\equiv -1}$で${\displaystyle \operatorname {GF} (2^{n}+1)}$ そして${\displaystyle {\sqrt {2}}\equiv -1}$で${\displaystyle \operatorname {GF} (2^{n+2}+1)}$これらの候補者については、${\displaystyle \theta ^{N}\equiv -1}$有限の場の下で、したがって我々の望むように行動する。

ただし、 θが有限体の1の根である限り、同じFFTアルゴリズムを引き続き使用できます。

FFT/NTT変換を求めるには、以下の手順を実行します。

${\displaystyle {\begin{aligned}C_{k}'&={\hat {f}}(k)={\hat {f}}\left(\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\right)\\[6pt]C_{k+k}'&={\hat {f}}(k+k)={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(A_{k\leftarrow k}\right)\bullet {\hat {f}}(B_{k\leftarrow k})+{\hat {f}}(A_{k\leftarrow k+n})\bullet {\hat {f}}(B_{k\leftarrow k+n})\end{aligned}}}$

最初の製品は${\displaystyle c_{k}}$各kについて。2 は、${\displaystyle c_{k}}$、 により${\displaystyle (i+j)}$モジュール${\displaystyle N(n)}$。

逆の操作を行うには：

${\displaystyle C_{k}=2^{-m}{\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$または${\displaystyle C_{k}={\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$

データの正規化が必要かどうかによります。

1つは${\displaystyle 2^{-m}}$FFTデータを特定の範囲に正規化するために、${\displaystyle {\frac {1}{n}}\equiv 2^{-m}{\bmod {N}}(n)}$ここで、mはモジュラー乗法逆数を用いて求められます。

シェーンハーゲ・シュトラッセンアルゴリズムでは、${\displaystyle N=2^{M}+1}$これは、値が にある二分木と考えるべきです。${\displaystyle 0\leq {\text{index}}\leq 2^{M}=2^{i+j}}$.${\displaystyle K\in [0,M]}$各Kに対して、すべてを見つけることができる${\displaystyle i+j=K}$、そしてすべてをグループ化します${\displaystyle (i,j)}$ペアをM個の異なるグループに分けます。${\displaystyle i+j=k}$グループ化${\displaystyle (i,j)}$畳み込みによるペア生成は、アルゴリズムにおける古典的な問題である。^{[ 9 ]}

これを踏まえて、${\displaystyle N=2^{M}+1}$グループ化を手伝ってください${\displaystyle (i,j)}$の中へ${\displaystyle {\frac {M}{2^{k}}}}$深さkのサブタスクの各グループをツリーでグループ化し、${\displaystyle N=2^{\frac {M}{2^{k}}}+1}$

注目してください${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$あるLに対して。これによりNはフェルマー数となる。modを実行すると${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$フェルマー環が存在する。

フェルマー数の中にはフェルマー素数であるものもあるため、場合によっては計算を省略できる。

もちろん、同じ素数の利点を持つ他のNも使用できます。${\displaystyle N=2^{k}-1}$バイナリ数で最大の数を持つ${\displaystyle k+1}$ビット。 ${\displaystyle N=2^{k}-1}$はメルセンヌ数であり、場合によってはメルセンヌ素数となる。フェルマー数に対する自然な候補である。${\displaystyle N=2^{2^{L}}+1}$

以下の式は、効率を計算することで、ビットサイズNが与えられた場合に適切なK ( Nビットを分割するグループ数) を見つけるのに役立ちます。^{[ 13 ]} 

${\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}}$Nはビットサイズ（${\displaystyle 2^{N}+1}$）最外層で。Kは${\displaystyle {\frac {N}{K}}}$ビットのグループ、${\displaystyle K=2^{k}}$。

nは、N、K、kを通じて、 最小のx を見つけることによって求められます。${\displaystyle 2N/K+k\leq n=K2^{x}}$

効率が50%以上だと仮定すると、${\displaystyle {\frac {n}{2}}\leq {\frac {2N}{K}},K\leq n}$そしてkは式の残りの部分に比べて非常に小さいので、

${\displaystyle K\leq 2{\sqrt {N}}}$

これは次のことを意味します。何かが非常に効果的な場合、Kは以下によって制限されます。${\displaystyle 2{\sqrt {N}}}$または漸近的に上方に制限される${\displaystyle {\sqrt {N}}}$

以下のアルゴリズム、標準的なモジュラー Schönhage-Strassen 乗算アルゴリズム (いくつかの最適化あり) の概要は^{[ 14 ]に記載されています。}

• T3MUL = トゥーム・クック乗算
• SMUL = シェーンハーゲ・シュトラッセン乗算
• 評価 = FFT/IFFT

実装の詳細については、『 Prime Numbers: A Computational Perspective 』 ^{[ 15 ]}を参照してください。このバリアントは、離散重み変換を利用してネガサイクリック畳み込みをより効率的に実行している点で、Schönhage の元の方法と多少異なります。詳細な情報については、Knuthの『The Art of Computer Programming』^{[ 16 ]}も参照してください。

ある一定のカットオフポイント以下では、 Toom–Cook乗算などの他の乗算アルゴリズムを使用する方が効率的です。^{[ 17 ]}

そのアイデアは、${\displaystyle {\sqrt {2}}}$秩序の統一の根源として${\displaystyle 2^{n+2}}$有限体において${\displaystyle \mathrm {GF} (2^{n+2}+1)}$（これは方程式の解です）${\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}}$）、NTT（数論的変換）アプローチで値を重み付けする場合。整数乗算時間を10%短縮できることが示されています。^{[ 18 ]}

許可することで${\displaystyle m=N+h}$計算できる ${\displaystyle uv{\bmod {2^{N}+1}}}$そして${\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2}}^{h})}$中国剰余定理（CRT）と組み合わせて、乗算uvの正確な値を求める。^{[ 19 ]}