2
$\begingroup$

I wish to do arithmetic on elements in an integer subring of a cyclotomic number field, i.e, in $\mathcal{O}_K = \mathbb{Z}(\zeta) \cong \mathbb{Z}[X] / <\phi_m(x)>$ where $\zeta$ is a root of the m'th cyclotomic polynomial $\phi_m(x)$ . As example, take $\zeta_8$ an 8th root of unity and the ring $\mathbb{Z}_p(\zeta_8) \cong \mathbb{Z}_p[X] / <x^4 +1>$ for an odd integer $p$. This is a common setup for ring-LWE (but with higher ring dimension and large modulus)

I am trying to do this with Victor Shoup's Number Theory Library (NTL v11.5) and trying to determine the appropriate class to use for this. I tried instantiating ZZ_pE and using the init() method in this class to to set the minimal polynomial for this extension ($x^4 + 1$). Having done this, I'm not sure about how to define elements in this ring and do arithmetic. Any pointers would be appreciated. Cross posted to NTL github page.

$\endgroup$
1
  • $\begingroup$ Cross-posting as indicated is allowed, but please self-answer if you receive an answer on the github page (contribute answer and link)! $\endgroup$
    – Maarten Bodewes
    Nov 22, 2023 at 12:02

1 Answer 1

2
$\begingroup$

Operations on $R_p = \mathbb{Z}_p[X] /< \phi_m(x)>$ are usually implemented using double-CRT representation (aka RNS), because the integer modulus $p$ is typically big. If it is small in your applications, then you just need "one level of CRT", namely, the NTT.

That is, you represent your elements as polynomials, then apply the NTT to them. Remember that if your NTT is defined over $\mathbb{Z}_p^N$, then, for $a, b \in R_p$, it holds that $$ NTT^{-1}(NTT(a) \odot NTT(b)) = (N \cdot a \cdot b \pmod{X^N - 1}) \pmod p $$ thus the reductions modulo $p$ are already performed and you just have to care about the reduction modulo $\phi_m(x)$.

There are different ways of doing that... The easiest one is to consider $m$ as a power of two, forcing $\phi_m(x)$ to be $X^N + 1$ where $N = m/2$. Then, there is a very simple preprocessing you can apply to both $a$ and $b$ and a similar postprocessing you apply after the inverse NTT and, voilà, you obtain reduction modulo $X^N + 1$ instead of $X^N - 1$ (this technique is called negacyclic NTT or negacyclic convolution and is also explained in the paper I linked above).

So, all that said, if you want your operations to be efficient, it is better to avoid using NTL classes that implement those rings and just stick with vectors over ZZ_p or over ZZ (especially if you have more than one prime), or even simple vectors of 32- or 64-bit integers, if you prime is small enough to fit on it.

By the way, HElib uses NTL, so you can check their code to get some inspiration.

$\endgroup$
3
  • $\begingroup$ with / $R_p = \mathbb{Z}_p[X] /< \phi_m(x)>$ or with \langle \ranlge $R_p = \mathbb{Z}_p[X] /\langle \phi_m(x)\rangle$. Which one is more common? $\endgroup$
    – kelalaka
    Nov 23, 2023 at 19:48
  • $\begingroup$ Usually \langle etc is preferred $\endgroup$
    – kodlu
    Nov 23, 2023 at 22:55
  • $\begingroup$ Thanks for the references I will check them out. $\endgroup$ Nov 26, 2023 at 18:46

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.