2

Description: to multiply the "complex unit" $w^{N/4}$ over a prime field, i.e., $w^N \equiv 1 \bmod (\,p)$ (suppose $p, N$ do provide such primitive root).

  1. I am implementing the radix-4 Number Theoretic Transform which involves the multiplications with the complex unit "$j$".
  2. It seems that in the complex domain, multiplication with the complex unit is "almost" free, i.e., $a + bj \to -b + aj$. That is one of the reasons that radix-4 FFT can save more number of multiplications compared with the radix-2 implementation.
  3. However, over the prime field, I have no idea whether this free multiplication is possible or not.

Thanks.

Fionser
  • 21
  • 1
    No, I mean for complex numbers, we only need to switch its real part and image part for multiplying with $j$, which is almost free. However, for a prime field, the $j$ is given as an integer $\alpha^{q-1/4}$. To multiply $\alpha^{q-1/4}$ with any element in the prime field, it seems we need to do the expensive integer multiplication followed with a modulus correction step. – Fionser Jan 21 '19 at 09:59

0 Answers0