3

こんにちは！

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

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

/// <summary>
/// Calculates the result of the recursive Number Theoretic Transform.
/// </summary>
/// <param name="coefficients"></param>
/// <returns></returns>
private static BigInteger[] Recursive_NTT_Skeleton(
    IList<BigInteger> coefficients, 
    IList<BigInteger> rootsOfUnity, 
    int step, 
    int offset)
{
    // Calculate the length of vectors at the current step of recursion.
    // -
    int n = coefficients.Count / step - offset / step;

    if (n == 1)
    {
        return new BigInteger[] { coefficients[offset] };
    }

    BigInteger[] results = new BigInteger[n];

    IList<BigInteger> resultEvens = 
        Recursive_NTT_Skeleton(coefficients, rootsOfUnity, step * 2, offset);

    IList<BigInteger> resultOdds = 
        Recursive_NTT_Skeleton(coefficients, rootsOfUnity, step * 2, offset + step);

    for (int k = 0; k < n / 2; k++)
    {
        BigInteger bfly = (rootsOfUnity[k * step] * resultOdds[k]) % NTT_MODULUS;

        results[k]          = (resultEvens[k] + bfly) % NTT_MODULUS;
        results[k + n / 2]  = (resultEvens[k] - bfly) % NTT_MODULUS;
    }

    return results;
}

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

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

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

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

BigInteger bfly = (rootsOfUnity[k * step] * resultOdds[k]) % NTT_MODULUS;        

results[k]          = (resultEvens[k] + bfly) % NTT_MODULUS;
results[k + n / 2]  = (resultEvens[k] - bfly) % NTT_MODULUS;

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

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

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

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

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

4

3 に答える 3

0

団結の根が実際に存在することを確認しなければなりません。Rには、1 と -1 の 2 つの根しかありません。これは、x^n=1 が真になる可能性があるのは、1 と -1 の 2 つだけです。

Cでは無限に多くの 1 の根があります: w=exp(2*pi*i/N) は 1 の基本的な N 乗根であり、0<=k の場合はすべて w^k です。

今あなたの問題に: あなたが作業しているリングが同じ特性を提供することを確認する必要があります: 団結の十分な根。

Schönhage と Strassen ( http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm ) は、2^N+1 を法とする整数を使用します。このリングには団結の根が十分にあります。2^N == -1 は 1 の 2 乗根、2^(N/2) は 1 の 4 乗根などです。さらに、これらの 1 の根には、2 の累乗であり、2 進シフトとして実装できるという利点があります (モジュロ演算は後で加算/減算になります)。

QuickMul ( http://www.cs.nyu.edu/exact/doc/qmul.ps ) は modulo 2^N-1 で動作すると思います。

于 2012-12-12T10:55:14.683 に答える