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

CC BY-SA 4.0
2024-05-08T18:11:28.977Z
2024-05-08T18:11:28.977Z
Naysh
<p>Let <span class="math-container">$q  = p^\ell$</span> be a positive integer power of a prime <span class="math-container">$p$</span>, of size  <span class="math-container">$q = \text{poly}(n)$</span>.</p>
<p>Over the Word-RAM model (with words of size <span class="math-container">$O(\log n)$</span>), how quickly can we perform addition and multiplication over the finite field <span class="math-container">$\mathbb{F}_q$</span>? In particular, can addition and multiplication be done in <span class="math-container">$O(1)$</span> time over the Word-RAM model? If this is not possible for general <span class="math-container">$q$</span>, is it possible when <span class="math-container">$q = 2^\ell$</span> is a power of two? Is there a standard reference for the complexity of these operations?</p>
<p>For concreteness, in this question, assume we already have access to a polynomial <span class="math-container">$f(x)$</span> of degree <span class="math-container">$\ell$</span> which is irreducible over <span class="math-container">$\mathbb{F}_p$</span>, so that <span class="math-container">$\mathbb{F}_q \cong \mathbb{F}_p / \langle f\rangle$</span>.</p>

CC BY-SA 4.0
2024-05-07T17:12:07.973Z
I don't know if this is the latest, but in the circuit model https://doi.org/10.1007/s10958-013-1350-5 gives a nice overview (from 2013).
Joshua Grochow
<cc.complexity-theory><ds.algorithms><algebra><algebraic-complexity><finite-fields>
Reference request: finite field computation over the Word-RAM model
Naysh
# Reference request: finite field computation over the Word-RAM model

(Asked by: username_0 on 2024-05-07)

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$.

**Tags:** cc.complexity-theory, ds.algorithms, algebra, algebraic-complexity, finite-fields
> **Comments:**
> **username_1**: I don't know if this is the latest, but in the circuit model https://doi.org/10.1007/s10958-013-1350-5 gives a nice overview (from 2013).  

---

## 1 answers

### Answer by username_0 on 2024-05-08. Score: 4

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).


---

