Comment by noam_k
2 years ago
Amazing summary, Jeremy!
One nitpick is regarding the double-CRT: you are referring to the RNS encoding, when the original paper[0] uses the term to talk about how polynomials are stored for fast computation. It's a nice philosophical view of decomposing the polynomial Φm(X) into products X − ζi the same way that the integer modulus Q is decomposed into primes. So it's more like one CRT on the coefficients, and another implemented as a DFT.
This may be some nuance I'm not quite getting still. You're saying that even if you use the coefficient encoding, one would still have reason to store polynomials in the CRT domain. I agree that would be more performant, but it seems not useful because then your element-wise products only ever correspond to convolutions (as I mention in the article). As far as I can tell, everyone does Double-CRT with RNS encoding, but I may be mistaken.