整数リングでFFTを使用して、長整数に任意のBASEの桁を掛ける必要があります。オペランドの長さは、kの場合は常にn = 2^kであり、畳み込みベクトルの場合は2nの成分があるため、2n'thの1の原始根が必要です。整数リングでFFTを使用した乗算
私は特に効率の問題には関心がありませんので、Strassen &Schönhageのアルゴリズムを使用したくないです。ちょうど基本畳み込みを計算した後、いくつかの値を持ちます。
それは、多くの数学者に簡単なようでいても、代数の私の理解は本当に悪いですので、私は質問の多くを持っている：
整数リングでFFTを実行する間の本質的な違いやニュアンスが
2^n + 1を法が何でありますか（おそらく複合）と整数FIELDSをモジュロのいくつかのプライムp？
2^n == -1 (mod 2^n+1)のように2が(2n)thというように、このようなリングにユニティの原始根であるので、これを頼みます。対照的に、整数フィールドでは、このような原始的な根を検索する必要があります。
FFTにこのようなフォームのリングを使用できないようなニュアンスがあります。整数リングを選択した場合、このフィールドには
2^n第1番目のルートが存在するのに十分な条件はありますか？
小さいための団結の他のすべての2^k番目の根が右、このルートを二乗することによって得ることができた？..不可欠制限がリングの剰余乗算に課されているもの？おそらく長さに、おそらく数値ベースに、多分乗算に使用される数値型でさえ。
畳み込みの係数がモジュロ演算によって減少すると、情報が失われる可能性があります。本当ですか、なぜですか？これを避ける一般的な条件は何ですか？- FFTベクトル、自社の製品や畳み込みベクトルのために十分であろうだけでプリミティブ型指定された動的リスト（すなわち
long）任意の可能性はありますか？または、係数をBigIntegerに変換する必要がありますか（実際にはどうすればよいでしょうか？）
これらの質問に対する一般的な回答に時間がかかりすぎる場合は、以下の条件での回答で特に満足します。フィールドZ_70383776563201に2^30までのオーダーの団結の原始根のテーブルをIを見つけた：
http://people.cis.ksu.edu/~rhowell/calculator/roots.html
私は長さ2^29の数を乗算する団結の2^30番目のルートを使用するのであれば、精度は何ですか/アルゴリズム的/効率的なニュアンスを検討する必要がありますか？
ありがとうございました！ 私は最高の答えに賞金を授与するつもりです - いくつかの例を手伝ってください。
より理論的な数値解析の質問はここをクリックしてください：http://scicomp.stackexchange.com/ – tskuzzy
これは非常に高度な質問です。私はおそらく、この分野で実際の実践経験を持つ少数の人々の1人ですそれに答えることができる。しかし、SOに答えられるには大きすぎます。それは、ページとテキスト+図のページを必要とするだろう... – Mysticial
私は見る...しかし、証拠のない基本的な事実は、この多くのページを取るだろうか？たぶん、証明のために、私はあなたの助けを借りて方向を見つけることができました。また、私は特に私に関係する質問の最後に特別な制限を置いています。私はいくつかのビールを、特にこれほど深くはない方法でこれに答える彼に借りている。 – wh1t3cat1k