数论变换（NTT）

《应用后量子密码学》本章的全部代码：共 2 段，其中 2 段可在此运行。编辑任意单元格，然后点击运行。

书中的代码片段在一章之内层层相依，但 Sage Cell 内核每次只运行一个单元格，运行后不保留任何状态，因此每个单元格都会用 apqc_book 重放此前的代码。这一调用是在书中原有代码之外唯一添加的内容。

← 在线演练

代码 1：在玩具域中寻找单位根

𝔽₁₇ 的非零元素构成一个 16 阶群。若 g 是生成元，则 g² 的阶为 8，可以作为 8 点循环 NTT 的 ω。SageMath 可以直接检验这一条件：

代码 2：一个完整的玩具版循环 NTT

下面的 SageMath 程序在循环环 𝔽₁₇[x]/(x⁸-1) 中完整地执行正变换、逐点乘积和逆变换。它有意只是一个玩具模型，而不是 ML-KEM。