私は、一般的な FFT の実装に関しては少し初心者ですが、基本的なアイデアのほとんどは理解できていると思います。この特定のケースでは、257 有限体で数論変換を実装しました。これは基本的に、典型的な基数 2 の Cooley-Tukey FFT です。私が知りたいのは次のいずれかです: この特定の NTT を効率的に実行するのにより適した、Cooley-Tukey Radix-2 に代わる良い方法はありますか?この質問、私はどちらかについて聞くことに興味があります)、またはより一般的なケースよりも効率的な実装を可能にするメルセンヌ NTT に固有のものはありますか?
1113 次
1 に答える
0
2 進長の FFT では、Cooley-Tukey に勝るものはないと思います。
これは、メルセンヌ数とは直接関係がなく、モジュラスを持つ任意の数値フィールドが対象となります2^(m*2^n)+1。I=2^(m*2^(n-1))は複素単位 でI^2=2^(m*2^n)=-1 mod (2^(m*2^n)+1)あり、q=2^(2*m)は 1 の原始2^n乗根です。
2 番目のポイントのインスピレーションについては、Schönhage: Asymtotically fast algorithm for the numeric multiplication ... のセクション1を参照してください。
于 2015-03-30T08:47:22.077 に答える