問題タブ [ntt]

こんにちは！

既に持っている単純な再帰的 FFT 実装に基づいて NTT アルゴリズムを開発しようとしています。

次のコードを考えてみcoefficientsましょう ( ' 長さmは正確に 2 のべき乗です)。

複雑なFFTで機能しましBigIntegerた（複雑な数値型に置き換えます（私は自分で持っていました））。統一の原始根を見つける手順を適切に変更したにもかかわらず、ここでは機能しません。

おそらく、問題は次のとおりです:渡されたパラメーターには、もともと次の順序で 1 の複素根のrootsOfUnity最初の半分しか含まれていませんでした:m

omega^0 = 1, omega^1, omega^2, ..., omega^(n/2)

これらの 3 行のコードでは次のようになっているため、これで十分でした。

私はもともと、任意のレベルの再帰 (任意のnandの場合i) で、 unity の複素根であるという事実を利用しました-omega^(i) = omega^(i + n/2)。

しかし、その性質は明らかに有限体では成立しません。しかし、根の前半だけを計算できる類似のものはありますか?

または、サイクルを から まで拡張し、n/2すべての1 乗根をn事前に計算する必要がありますか?m

たぶん、このコードには他の問題がありますか? ...

事前にどうもありがとうございました！

私は、一般的な FFT の実装に関しては少し初心者ですが、基本的なアイデアのほとんどは理解できていると思います。この特定のケースでは、257 有限体で数論変換を実装しました。これは基本的に、典型的な基数 2 の Cooley-Tukey FFT です。私が知りたいのは次のいずれかです: この特定の NTT を効率的に実行するのにより適した、Cooley-Tukey Radix-2 に代わる良い方法はありますか?この質問、私はどちらかについて聞くことに興味があります)、またはより一般的なケースよりも効率的な実装を可能にするメルセンヌ NTT に固有のものはありますか?

次のコードの複数の where 条件により、最初の行のみが表示されます。

この条件に一致する行をすべて表示したいのですが、

単一の条件でも、最初の行のみが表示され、すべての行を表示するにはどうすればよいですか。