# Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$?

I want to implement some (lattice based) protocols to better familiarize myself with a programming language (Rust). These tend to do arithmetic over rings like $$\mathbb{Z}/m\mathbb{Z}$$, or "extensions" of this ring (meaning $$(\mathbb{Z}/m\mathbb{Z})[x] / (f(x))$$. Since it seems like I'll need to implement the ring arithmetic myself (there are finite field libraries, but this stops certain optimizations I am interested in exploring such as double-CRT arithmetic), I might as well do something slightly-more-than-naive, and use constant time algorithms (which I am assuming are quite well-known at this point). I am somewhat interested in algorithms that assume special structure of $$m$$ and $$f(x)$$ (say $$m = 2^k \pm c$$ for small $$c$$, or $$f(x)$$ a cyclotomic polynomial), but my primary interest is of algorithms that make no special assumptions on the structure of $$m$$ or $$f(x)$$.

Is there a particularly good reference for these algorithms? Chapter 14 of Handbook of Applied Cryptography seems to be a good start. It doesn't appear to discuss polynomial arithmetic directly, but it seems like you could piece together something by using their MPI arithmetic section. Additionally, this chapter doesn't discuss constant time algorithms directly, but quickly glancing over their algorithms I don't see anything that is too obviously variable time.

Still, is there some better reference for the task I am interested in?

• Joining the Rust wave. Jan 16, 2021 at 22:40

I have not yet looked into algorithms for $$\mathbb{Z}/n\mathbb{Z}[x]$$ or $$\mathbb{Z}/n\mathbb{Z}[x]/(f(x))$$, so won't accept an answer until I get to there (or someone else suggests references).