# Any Efficient Multiplication with a Primitive Root over Prime Field?

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.

• 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? – Morgan Rodgers Jan 21 at 5:40
• @MorganRodgers Suppose that a such complex unit do exist, such as when $p = 1 \bmod 2N$. Thank your for the answer. – Fionser Jan 21 at 5:51
• 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? – Morgan Rodgers Jan 21 at 6:20
• 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 at 9:59
• Usually finite field multiplication is done using a table lookup (see Zech's logarithms). – Morgan Rodgers Jan 21 at 17:23