面向 Saber 算法的任意模 NTT 乘法器

吕 　杰
浙江邮电职业技术学院

摘要

在后量子算法竞赛中，Saber算法具有抵御量子计算攻击的特性，但其多项式商环存在模乘运算复杂度高、非质模数约束等问题。通过对中国剩余定理（Chinese Remainder Theorem，CRT）和数论变换（Number Theoretic Transforms，NTT）的研究，本文提出高性能任意模乘法器设计方案。在分析模乘运算的质模数耦合的基础上，首先利用 CRT 构建三组同余方程，扩充数值边界以降低质模数的约束 ;然后采用数论变换的方式将模乘运算分解成 N 级蝶形电路 ; 实现低计算复杂度任意模的 NTT 乘法器。在 TSMC 65nm 工艺下进行仿真，实验结果表明，所设计的乘法器面积为 1.258mm2
，功耗为 9.84mW，工作频率为 20MHz。

关键词

Saber 算法；中国剩余定理；数论变换；模乘法器

参考

[1] 吕杰，汪鹏君，张会红 . 面向 Saber 算法的并行乘法器 [J].宁波大学学报（理工版），2022，35（06）：15-21.

[2]刘星杰 .后量子密码算法 Saber的高效硬件实现 [D].湖北省：华中科技大学，2021.

[3] 华中科技大学 . 多项式乘法器及具有该乘法器的处理器：CN114371828B[P/OL].2024-07-26[2025-02-18]. https：//www.cqvip.com/doc/patent/3463100113.

[4] 范建南，高献伟，薛文瀚 .Saber 算法的多项式乘法 FPGA实现研究 [J]. 北京电子科技学院学报，2022，30（01）：20-31.