c# - 使用有限域 FFT 的多项式乘法 - 选择第 n 个原单位根

Question

作为一项学校作业，我应该用 C# 创建一个程序，在有限域上使用 FFT 将两个多项式相乘。
我选择的有限域是 Z_p(所有操作模 p，元素是 {0,...,p - 1})。我意识到 p 必须足够大，这样生成的多项式中的因子才不会因模运算而改变。
对于较小的 n(在相应的有限域中)，找到第 n^th 个原单位根很容易。但是，我需要为 n = 2²⁰ 找到它。我实际上只需要这个，因为计算 2 的所有较低次幂是通过平方来完成的。我试图编写一个简单的程序来计算它(利用有限域 Z_{c*2^r 中有 2^r 个单位根这一事实+ 1}), 运行了很长时间但没有完成。所以我试着谷歌一些东西，只在字段 Z_{70383776563201 中找到了 n = 2^k 对于 k = 0..30 的原始 n^th 根表} 并使用了它。当然，当我使用 longint 时，它会导致溢出，因此导致错误的答案。所以我开始使用 System.Numerics 命名空间中的 BigInteger 结构。这就是我所在的地方，有一个非常慢的正确算法:

private static List<BigInteger> FFT(List<BigInteger> input, BigInteger Omega)
            {
                if (input.Count == 1)
                {
                    return new List<BigInteger>() { input[0] };
                }
                else
                {
                    List<BigInteger> evenInput = new List<BigInteger>();
                    for (int i = 0; i < input.Count; i += 2)
                    {
                        evenInput.Add(input[i]);
                    }
                    List<BigInteger> oddInput = new List<BigInteger>();
                    for (int i = 1; i < input.Count; i += 2)
                    {
                        oddInput.Add(input[i]);
                    }
                    List<BigInteger> even = FFT(evenInput, (Omega * Omega));
                    List<BigInteger> odd = FFT(oddInput, (Omega * Omega));
                    BigInteger[] outputArr = new BigInteger[input.Count];
                    int count = 0;
                    for (int i = 0; i < input.Count / 2; i++)
                    {
                        outputArr[i] = (even[i] + BigInteger.Pow(Omega, i) * odd[i]);
                        outputArr[i + input.Count / 2] = (even[i] - BigInteger.Pow(Omega, i) * odd[i]);
                        count += 2;
                    }
                    List<BigInteger> output = new List<BigInteger>();
                    for (int i = 0; i < count; i++)
                    {
                        output.Add(outputArr[i] % finiteField);
                    }
                    return output;
                }
            }

我知道创建所有列表无助于提高速度，但主要问题当然是 BigInteger 结构。(我尝试了与 System.Numerics.Complex 结构基本相同的代码，它的速度达到了应有的速度be) 模运算需要很长时间，所以我知道我必须回到 longint。问题是找到原始的 n^th 单位根。我不知道是否有可能将第 2²⁰ 个单位原根与 longint 一起使用而不必担心溢出。如果不是，我可以为哪个 n 使用 longint 并因此有一个快速算法？
有没有一种方法可以更快地计算大 n 的原根？也许有人知道有限域中预先计算的原始根表？或者我应该考虑使用其他有限域吗？这是我所知道的唯一一种。我已经搜索了很长时间，但没有找到任何有用的东西。老师告诉我，这方面有据可查，但似乎并非如此。

Answer 1

我还没有完全考虑清楚，但似乎在切换到 BigIntegers 时你不应该看到那么大的差异——也许是 10 倍？你做数学模型 2^20，所以你的数字应该保持很小。在我看来，这些是您的问题:Omega * Omega，尤其是 even[i] + BigInteger.Pow(Omega, i) * odd[i]。这将使您的数字增长得比他们需要的大得多。

Biginteger.Pow 在指数长度上有一个指数运行时间。您正在进行模块化数学运算，因此您应该能够更频繁地减少模 finiteField:Omega * Omega % finiteField 和 even[i] + BigInteger.ModPow(Omega, i, finiteField ) * 奇数[i].