2
$\begingroup$

While debugging an NTT implementation I've noticed something. Looks like if I have a primitive $(n = 2^k)$-th root of unity $\omega$ in a $GF(p)$, then

$\omega ^0 = -\omega ^{n/2} + p,$

$\omega ^1 = -\omega ^{n/2 + 1} + p,$

$...$

$\omega ^{n/2 - 1} = -\omega ^{n-1} + p.$

Or, maybe, I could rewrite it as

$\omega ^i \equiv \omega ^ {n/2 + i} \mod p \quad \forall i=1..n/2-1$.

Does it always hold? Why? Does it hold under stronger conditions (e.g. for all even $n$, not just $n = 2^k$)?

Thank you very much in advance!

1 Answers 1

2

In $GF(p)$ we have characteristic $p$ so the $+p$ appended at the end of each equation is superfluous.

Otherwise notice that each of the subsequent equations follow by multiplying the first equation by a power of $\omega$. It suffices therefore to demonstrate the first equation.

Since $\omega^n=1$ and $n$ is even, factoring yields $(\omega^{n/2}+1)(\omega^{n/2}-1)=0$. Because this is a field and so has no zero divisors, we find that $\omega^{n/2}=\pm1$, but $\omega^{n/2}=+1$ would contradict the hypothesis that $\omega$ is a primitive root of unity, so we must have $\omega^{n/2}=-1$. Note this works for any even $n$.

  • 0
    A brilliant clarification. Thanks a lot!2012-04-22