4
$\begingroup$

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$.

Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and multiplication over the finite field $\mathbb{F}_q$? In particular, can addition and multiplication be done in $O(1)$ time over the Word-RAM model? If this is not possible for general $q$, is it possible when $q = 2^\ell$ is a power of two? Is there a standard reference for the complexity of these operations?

For concreteness, in this question, assume we already have access to a polynomial $f(x)$ of degree $\ell$ which is irreducible over $\mathbb{F}_p$, so that $\mathbb{F}_q \cong \mathbb{F}_p / \langle f\rangle$.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first spend some $O(q^\varepsilon)$ preprocessing time, for some arbitrarily small constant $\varepsilon > 0$ (and this preprocessing is not necessary if $q = p$ is a prime).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.