1
$\begingroup$

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it create problems for the system?

$\endgroup$
2
  • $\begingroup$ While the ring of integers modulo $q$ is a field iff $q$ is prime, there are finite fields with $q$ elements for some other $q$, specifically for $q$ a prime power. Is the question about replacing the finite field $\mathbb F_q$ for prime $q$ by (A) the ring of integers modulo a composite $q$, or (B) the field $\mathbb F_{p^k}$ for prime $p$ and $k>1$ ? $\endgroup$
    – fgrieu
    Commented Jul 28, 2023 at 12:16
  • $\begingroup$ Similar question with an answer. $\endgroup$
    – fgrieu
    Commented Jul 28, 2023 at 13:41

1 Answer 1

1
$\begingroup$

It is not only fine for $q$ to be composite, but it is common. In some applications of lattice-based cryptography, one requires $q$ to be large (say $\gg 2^{64})$ for correctness. There are two ways to compute arithmetic of this type

  1. Via "big-integer" arithmetic, i.e. in software implementing arithmetic modulo $q:= 2^{400}+c$ or whatever, and
  2. Via "Chinese remainder theorem arithmetic", i.e. in software implementing arithmetic modulo $q = \prod_i p_i$, for coprime $p_i$ of size $p_i < 2^{64}$.

Note that I say $2^{400}+c$ (rather than $2^{400}$) because one can gain efficiency from $q$ being a certain type of prime ("NTT-friendly", meaning $q\equiv 1\bmod 2n$, where $n$ is the RLWE ring degree). This has nothing to do with security though.

This later type of arithmetic is generally more efficient. This is because the chinese remainder theorem gives you an isomorphism of rings

$$\mathbb{Z}_q[x] / (f(x)) \cong \prod_i\mathbb{Z}_{p_i}[x]/(f(x))$$

Moreover, this isomorphism (on the right-hand side) is such that both addition and multiplication are done "coordinate-wise", i.e. there are simple linear-time (in the number of $p_i$) algorithms to compute them, in comparison with having to track around carries, and use potentially $\Omega(\log q)$-time big-integer multiplication (for example, $\Theta((\log q)^{\approx 1.5})$ is typical, using what are known as "Evaluation-Interpolation" algorithms. Terms to search are Karatsuba, and Toom-Cook).

This is to say that CRT-techniques allow one to mostly fall back on hardware multipliers (rather than software), and moreover use linear time (rather than $\Theta((\log q)^{\approx 1.5})$-time) multiplication algorithms.

One then typically chooses the $p_i$ to all individually be NTT friendly, so you additionally get fast polynomial multiplication in each of the rings $\mathbb{Z}_{p_i}[x]/(f(x))$ (rather than fast integer multiplication, the only thing we have been discussing so far). The combination of these two optimizations is often called "Double CRT" or "Double RNS", where RNS means Residue Number System.

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