数论变换(NTT)由于其准线性复杂性被广泛认为是计算高维和积分系数多项式乘法的最有效方法。

广义分裂环数论变换

将原始多项式拆分为低次多项式组而构造的NTT变体，如K-NTT、H-NTT和G3-NTT，它们之间有什么关系?它们是否可以看作是某种算法在不同参数化下的特殊情况?

为了解决这些问题，赵云雷领导的研究小组于2024年8月15日在《计算机科学前沿》杂志上发表了新的研究成果。

研究团队提出了第一个广义分裂环数论变换，简称GSR-NTT。然后，他们研究了K-NTT、H-NTT和G3-NTT之间的关系。

他们在研究中研究了基于首一增量多项式簇的广义分裂环多项式乘法，并提出了第一个广义分裂环数论变换，简称为GSR-NTT。他们证明了K-NTT、H-NTT和G3-NTT在不同参数化下可以视为GSR-NTT的特例。

他们介绍了一种简洁的复杂性分析方法，GSR-NTT 可以在此基础上得出其最佳参数设置。他们为 GSR-NTT 提供了基于循环卷积多项式和三次幂循环多项式的其他实例。

他们利用 GS​​R-NTT 加速了基于格的方案 NTTRU 中的多项式乘法和三次幂分圆多项式环上的单多项式乘法。实验结果表明，对于 NTTRU，GSR-NTT 分别使密钥生成、封装和解封装算法的加速比为 24.7%、37.6% 和 28.9%，总加速比为 29.4%。

未来的工作可以集中在更多平台上实施 GSR-NTT。