2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Finite field multiplication is always almost free when representing elements as powers of a primitive root. Also, you don't always have a "complex unit" (i.e., -1 is not always a square). So maybe you can clarify what you are asking? $\endgroup$ – Morgan Rodgers Jan 21 at 5:40
  • 1
    $\begingroup$ @MorganRodgers Suppose that a such complex unit do exist, such as when $p = 1 \bmod 2N$. Thank your for the answer. $\endgroup$ – Fionser Jan 21 at 5:51
  • 1
    $\begingroup$ Then yes, if $\alpha$ is primitive element of $\mathbb{F}_{q}$ and $j = \alpha^{\frac{q-1}{4}}$ then $j^{2} = -1$ and so $j(a+bj) = -b+aj$. Is this what you are asking? $\endgroup$ – Morgan Rodgers Jan 21 at 6:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Fionser Jan 21 at 9:59
  • 1
    $\begingroup$ Usually finite field multiplication is done using a table lookup (see Zech's logarithms). $\endgroup$ – Morgan Rodgers Jan 21 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.