Correct me if i am wrong, in the finite field ℤ/pℤ there exist a primitive root of order p-1 which is also a (p-1)th root of unity modulo n. Thus to evaluate a N degree polynomial, where N is a power of 2, at (p-1)th roots of unity modulo n, we require p-1 = N = 2^k, or expressed in another way,
p = 2^k + 1.
But some online sources cite, p = m * (2^k) + 1 for m > 0.
Question- Now i don’t understand the purpose and benefit of putting ‘m’ into the equation, why not just p = 2^k + 1, how putting a ‘m’ other than 1 would help for our purpose of calculating NTT at various point
Its not wrong to use p=2^k+1 everywhere if we can find a k, but how many primes of this form really exist?
Using p = m*2^k+1 you can find primes corresponding to 2^k sizes and you can then calculate DFT of size 2^k. But the polynomial of degree n(power of 2) will now be evaluated at power of w where w=g^{(p-1)/n}.
Failed to understand the last line, suppose p = m * 2^k + 1, then to calculate DFT of size 2^k we would be considering the closed subgroup generated by an element ‘a’ such that | a | = 2^k, and thus implying a^(2^k) = 1 (mod n), am i right till here ? so wouldn’t we be calculating the polynomial at power so ‘a’, i.e, at w = (a^i) % mod n for 1 <= i <= 2^k ? which generator ‘g’ have you mentioned in the last ?
for example if p = 2 * (2^3) + 1 = 17 then to calculate DFT of length 8, wouldn’t we have to find a primitive root ‘a’ of 8 length closed subgroup ?.
for a = 2, 2^8 % 17 = 1 mod n, and thus primitive root of closed subgroup of length 8. Then, we can evaluate polynomial at 2^i for 1 <= i <= 8 right ? (at [2, 4, 8, 16, 15 13, 9, 1], in this example). You suggest that we can calculate it at powers of w = g^( (p-1) / n ) = g^(16/8) = g^2. i don’t know what ‘g’ is here. can you please explain it by extending it further ?