2

整数リングでFFTを使用して、長い整数に任意の数字のベースを掛ける必要があります。n = 2^kオペランドは常に一部の長さkであり、畳み込みベクトルには2nコンポーネントがあるため2n'th、ユニティの原始根が必要です。

私は効率の問題に特に関心がないので、Strassen & Schönhage のアルゴリズムを使用したくありません。基本的な畳み込みを計算し、次にキャリーを計算するだけです。

多くの数学者にとっては単純に思えるかもしれませんが、私の代数の理解は本当によくないので、たくさんの質問があります:

  1. 2^n + 1整数環モジュロ(おそらく複合) で FFT を実行する場合と、いくつかの素数を法とする整数 FIELDS でFFT を実行する場合の本質的な違いやニュアンスは何pですか?

    私がこれをお願いするの2は、(2n)thがそのようなリングにおける団結の原始根だから2^n == -1 (mod 2^n+1)です。対照的に、整数フィールドでは、そのような原始根を検索する必要があります。

    しかし、FFT にそのような形式のリングを使用することを妨げる他のニュアンスがあるかもしれません。

  2. 整数環を選んだ場合2^n、この体に 1 乗根が存在するための十分条件は何ですか?

    より小さい次数の 1の他のすべての2^k乗根は、この根を 2 乗することで得られますよね?.

  3. 環のモジュロによる乗算には、どのような本質的な制限が課せられますか? たぶん、それらの長さ、数値ベース、さらには乗算に使用される数値型についてです。

    畳み込みの係数がモジュロ演算によって削減されると、情報の損失が発生する可能性があると思います。それは本当ですか、なぜですか?.. これを回避できる一般的な条件は何ですか?

  4. プリミティブ型の動的リスト (つまりlong) だけで、FFT ベクトル、その積、および畳み込みベクトルに十分である可能性はありますか? それとも、念のために係数を変換する必要がBigIntegerありますか (そして、本当に必要な場合の「ケース」とは何ですか)?

これらの質問に対する一般的な回答に時間がかかりすぎる場合は、次の条件での回答に特に満足します。2^30フィールド Z_70383776563201までの順序統一の原始根の表を見つけました。

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

したがって2^30、長さの数を乗算するために th root of unity を使用する場合2^29、考慮すべき精度/アルゴリズム/効率のニュアンスは何ですか?..

よろしくお願いします！最良の回答には報奨金を授与します - いくつかの例を手伝うことを検討してください。

4

2 に答える 2

2

まず、あなたの身元についての算数の手がかり: 70383776563201 = 1 + 65550 * 2^30. そして、その長い数は素数です。ページには、モジュラスに関する多くの洞察がありますFFT 定数が見つかった方法。

これは、あなたが知っておくべき群論の事実です。N を法とする整数の乗法群は、次数が N の素因数によって決定される巡回群の積です。N が素数の場合、1 つの循環があります。ただし、このような巡回群の元の順序は、 の素因数に関連していN - 1ます。70383776563201 - 1 = 2^31 * 3^1 * 5^2 * 11 * 13、指数は要素の可能な順序を示します。

(1) 原始根は必ずしも必要ではありません。次数が少なくとも十分に大きいものが必要です。「高次」の要素を見つけるための確率的アルゴリズムがいくつかあります。それらは、鍵材料の強力なパラメーターを確保するために暗号化で使用されます。特に 2^n+1 の形式の数については、因数分解が注目されており、結果を調べることができます。

(2) 次数 2^n の要素の十分な (そして必要な) 条件は、モジュラスの例によって示されます。条件は、モジュラスのいくつかの素因数pが というプロパティを持たなければならないということ2^n | p - 1です。

(3) 情報の損失は、要素が乗法可逆でない場合にのみ発生します。これは、素数法の巡回乗法群には当てはまりません。複合モジュラスを持つモジュラーリングで作業する場合、一部の要素はそれほど可逆ではありません。

(4) の配列を使用したい場合はlong、基本的に大整数ライブラリを書き直すことになります。

于 2012-11-08T20:36:17.977 に答える