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

作为一项学校作业，我应该用C#创建一个程序，在有限域上使用FFT将两个多项式相乘
我选择的有限域是Z_p（所有运算都模p，元素是{0，…，p-1}）。我意识到p必须足够大，这样生成的多项式中的因子就不会因模运算而改变
对于小n（在相应的有限域中），找到单位的第n^个原始根是容易的。然而，我需要为n=2²⁰找到它。我实际上只需要这个，因为计算2的所有较低幂是通过平方来完成的。我试着写一个简单的程序来计算它（利用有限域Z_c*2^r+1中存在第2^r个单位根的事实），运行了很长时间，但没有完成。所以我试着用谷歌搜索一些东西，只在Z_{70383776563201}字段中找到了一个n=2^k的基元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结构中尝试了基本相同的代码，而且速度很快）模运算需要很长时间，所以我知道我必须回到longint。问题是找到单位的原始n^th根。我不知道是否有可能使用longint的第2²⁰个单位的原始根，而不必担心溢出。如果不是，对于哪个n，我可以使用longint，从而有一个快速算法
有没有一种方法可以更快地计算大n的原始根？也许有人知道有限域中预先计算的原始根的表？或者我应该考虑使用其他有限域吗？这是我所知道的唯一一种。我搜索了很长时间，没有发现任何有用的东西。老师告诉我，这个领域有很好的记录，但事实似乎并非如此。