FN-DSA（Falcon）：面向草案的讲解

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

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

← 在线演练

代码 1：SageMath 实验：公开的 NTRU 关系

Sage 可以验证 NTRU 格背后的公钥方程。本示例有意止步于高斯陷门采样器之前：找到一个分布正确的短签名是 FN-DSA 中困难且对规范敏感的部分，这个玩具计算并不复现它。

代码 2：求解 NTRU 方程。

密钥生成中唯一真正困难的步骤，就是书中的算法 中用一句话带过的那一行：求解 fG - gF = q，得到短的 F,G。方法是塔式递归。域范数 N 把 ℤ[x]/(x^n+1) 映射到 ℤ[x]/(x^n/2+1)；反复应用它便可到达 ℤ，在那里该方程就是一个扩展 gcd 问题；然后利用范数的乘法性把解逐层提升回来。