環の選択

ウィキペディア小見出し辞書

環の選択

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/28 23:15 UTC 版)

「ショーンハーゲ・ストラッセン法」の記事における「環の選択」の解説

離散フーリエ変換は、任意の代数環で実行できる抽象的な概念である。一般的には複素数において計算されるが、乗算の正確な結果を保証するため十分に高い精度で計算することは複雑な処理が必要になり、実行速度は遅くなる。ここではその代わりに、数論変換を行い、整数 N を用いて mod N において変換を実行する。 複素平面内にすべての1の冪根とその冪乗が存在するのと同じように、与えられた任意の位数 n に対して、うまく整数 N を選んで b が法 N における１の原始根となるようにできる（つまり、bn ≡ 1 (mod N) であり、かつ b の冪乗で指数が正でかつ n 未満のものはどれも mod N で 1 と合同にならない。） このアルゴリズムは、小さな数値の再帰的な乗算にほとんどの時間を費やす。それは素朴な実装では、以下のように多くの場所で発生する。 高速フーリエ変換において、原始根 b は繰り返して、累乗・自乗・（他の値との）乗算がされる。 重みベクトル A か逆の重みベクトル A−1 を他のベクトルに掛けるときには、重みベクトル A を形成するために原始根 a の累乗が計算される。 変換された２つのベクトルの間の成分ごとの積の計算。 ショーンハーゲ・ストラッセン法の鍵となる洞察は法 N の選択であり、ある整数 n を用いてN=2n + 1であるものを選ぶ。ここで n は変換を受けるブロックの数 P=2p の倍数である。このことから大きな整数を二進表現する標準的なシステムにおいては以下のような多くの利点が生じる： 任意の整数を法 2n + 1 で合同な数に還元することは、シフト演算と加算演算だけでできる。 環における全ての1の冪根は、 2k のかたちになる。そのことから、任意の数の1の冪根による乗算や除算は二進数のシフト演算になり、１の冪根の累乗や平方の計算は冪指数についての計算だけでできる。 変換された２つのベクトルの間の要素ごとの積の再帰的な計算は、逆向きの巡回畳み込みによってできる。この計算は線形畳み込みよりも高速であり、 mod (2n + 1 )での結果の還元は既にできているので手間が省ける。 再帰的な乗算の実行を便利に行うためには、ショーンハーゲ・ストラッセン法を、2つの整数の積を計算するだけではなくて、与えられた n に対するmod ( 2n + 1) での2つの整数の積の計算を行うものとして組み立てる。これによって一般性を失うことはない、なぜならば n を十分大きく選べば、mod(2n + 1 )での積が単に2つの整数の積となるようにできるからである。