Polynomial Multiplication Using a Finite FFT Field - Choosing the nth Primitive Root from One

Question

As a school assignment, I have to create a C # program that multiplies two polynomials using FFT over a finite field.
My final selection field will be Z _p (all operations modulo p, elements: { 0, ..., p - 1 }). I realized that p must be large enough so that the factors in the resulting polynomial do not change modulo.
Finding the primitive root n ^th of unity is easy for small n (in the corresponding finite field). However, I needed to find it for n = 2 ²⁰ . I practically needed only this, calculating it for all lower degrees 2, making a square. I tried to write a simple program that would calculate it (using the fact that in the final field 2 ^r th is the root of unity in the final field Z _{c * 2 ^r + 1} ), I missed it for a rather long time and did not finish it. So I tried something on Google and found a table of primitive n ^th for n = 2 ^k for k = 0..30 in the field Z _{70383776563201} and used it. Of course, when I used longint, this led to overflow and therefore incorrect answers. So I started using the BigInteger structure from the System.Numerics namespace. This is where I am, having the right algorithm, which is very slow:

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; } } 

I know that creating all lists does not help speed, but the BigInteger structure, of course, is the main problem. (I tried basically the same code with the System.Numerics.Complex structure, and it was as fast as it should be) The modulo operation is very time consuming, so I know that I need to go back to longint. The problem is finding the primitive root n ^th of unity. I don't know if it is even possible to use a primitive root of 2 ²⁰ out of one with longint without worrying about overflow. If not, why can n be used with longint and therefore have a fast algorithm?
Is there a way to compute primitive roots for large n faster? Maybe someone knows a table of precomputed primitive roots in finite fields? Or should I use other trailing fields? This is the only species that I know of. I searched for quite a while and did not find anything useful. Teacher told me that this area is well documented, but it seems that this is not so.

Answer 1

I did not think about it completely, but it seems you should not see that the big difference when switching to BigIntegers is maybe 10 times? You are doing a 2 ^ 20 math mod, so your numbers should stay pretty small. It seems to me that these are your problems: Omega * Omega , and especially even[i] + BigInteger.Pow(Omega, i) * odd[i] . This will allow your numbers to grow much more than they should be.

Biginteger.Pow has exponential runtime in exponent length. You do modular math, so you can most often reduce modulo finalField: Omega * Omega % finiteField and even[i] + BigInteger.ModPow(Omega, i, finiteField) * odd[i] .

Answer 2

You can work in a ring modulo 2 ⁿ +1, that is, numbers from 0 ... 2 ⁿ inclusive. Since 2 ⁿ == -1 (mod 2 ⁿ +1), and the square -1 is 1, 2 is the primitive (2 * n) ^th root of unity in this ring.

What's more, modulo mod 2 ⁿ +1 operations are easy to implement with shifts, adds subs. It is very cheap even with bonuses. Similarly, multiplications in powers of 2 naturally represent only shifts (plus the operation mod).

This is part of the idea of ​​the Schönhage-Strassen long integer multiplication algorithm . Wikipedia article is a good start.