負の多項式乗算

この記事では、格子暗号と完全ホモモルフィック暗号で登場する特殊な多項式積の3つの計算技巧をカバーします。具体的には、negacyclic 多項式積、つまり $\mathbb{Z}[x] / (x^N + 1)$ という商環での2つの多項式の積です。negacyclic 積の前駆者として、より簡単な cyclic 積もカバーします。 この記事で書かれたすべての Python コードは GitHub にあります。