Multiplication polynomiale négacyclique

Dans cet article, je vais aborder trois techniques pour calculer des types spéciaux de produits de polynômes qui apparaissent dans la cryptographie en treillis et le chiffrement homomorphe complet. Plus précisément, le produit de polynômes négacycliques, qui est le produit de deux polynômes dans l'anneau quotient $\mathbb{Z}[x] / (x^N + 1)$. En guise de précurseur au produit négacyclique, nous allons aborder le produit cyclique plus simple. Tout le code Python écrit pour cet article est disponible sur GitHub.