Page 334 - 《软件学报》2026年第7期

胡晓雯 等: 基于 CUDA Core 和 Tensor Core 的 CTRU-Prime 高吞吐量实现 3019

密码方案的底层代数结构具有一定要求, 一般将支持 NTT 操作的环称为 NTT 友好环. CTRU-Prime 的底层代数结
Z q [x]/(x − x−1), 具备不可分解性, 不支持一般的 NTT 操作. 因此, 优化加速素阶数域上的多项式乘
n
构为素阶数域
法存在一定的挑战. 本节首先基于 CUDA Core 设计了素阶数域拓展环上的伪梅森数不完整 NTT, 此外, 在完成素
阶数域多项式乘法的矩阵数学推导的基础上, 利用 GPU Tensor Core 的矩阵计算优势实现教科书式的多项式乘法.
3.1 基于 CUDA Core 的伪梅森数不完整 NTT 的多项式乘法
3.1.1 伪梅森数不完整 NTT 简介
文献 [12] 使用伪梅森数不完整 NTT 完成素阶数域上的多项式乘法, 表 2 为 CTRU-Prime 的伪梅森数不完整
n
NTT 参数表. 具体来说, 基于域扩张技术, 将素阶数域 Z q [x]/(x − x−1) 上的多项式乘法转移到 NTT 友好的拓展环
Z q ′[x]/(x −1) 上 q ( ′ 为具有 2 −2 +1 形式的伪梅森数), 且拓展环上的多项式乘法结果仅需进行简单的多项式模
x
y
N
运算即可回到原先的素阶数域上. 下面以 R q 上的多项式乘法 h = f ·g 为例, 介绍主体流程.
N
′
′
,
(1) 域扩张. 将 n 维多项式 f 和 g 的高次项补 0 扩充至 N 维, 得到多项式 f ,g ∈ Z q ′[x]/(x −1), 其中 N ⩾ 2n q ′
为某个足够大的素数使得它大于计算过程中多项式系数在 Z 上的最大值.
N
′
′
′
′ g 的正向 NTT 变换、点乘和逆向 NTT h = f ·g ∈ Z q ′[x]/(x −1). 需要注意的是, 由
′
(2) 计算 f 和 变换, 得到
于拓展环不具备完全可分解性, 在计算 N 维正向 NTT 变换和逆向 NTT 变换时, 使用伪梅森数不完整 NTT.
′ n R q 中相乘的结果. 需要注意的是, 域收缩过程的
(3) 域收缩. 计算 h = (h mod (x − x−1)) mod q, 即为 f 和 q 在
′
正确性由 N,q 的取值保证.

表 2 伪梅森数不完整 NTT 参数集

方案 参数 (n,q,q 2 ,η) N,q 的取值 FFT trick顺序
′
6
11
24
CTRU-Prime-653 (653,4621,2 ,3) (1344,16777153 = 2 −2 +1) 5层基2、1层基3、1层基2
12
10
25
CTRU-Prime-761 (761,4591,2 ,2) (1536,33550337 = 2 −2 +1) 9层基2
10
25
12
CTRU-Prime-1277 (1277,7879,2 ,2) (1344,16777153 = 2 −2 +1) 9层基2

3.1.2 基于 CUDA Core 的优化设计与实现
如上所述, 基于伪梅森数不完整 NTT 的多项式乘法主要包括 5 步: 域扩张、正向 NTT 变换、点乘、逆向 NTT 变
换和域收缩, 需从内存模式和线程组织形式两个角度考虑, 设计融合 5 个操作的基于 CUDA Core 的多项式乘法方案.
从内存延迟角度来看, 全局内存的访问延迟最高, 共享内存次之, 寄存器最少. 基于上述访存特点, 本文设计了
如图 1 所示的内存模式. 在该内存模式中, 仅有域扩张和域收缩需要和全局内存进行交互, 其余操作被转移到寄存
器和共享内存上, 从而有效提高了访存的效率. 进一步地, 在域扩张和域收缩的过程中, 合并对全局内存的访问, 以
提高 DRAM (dynamic random access memory) 的带宽利用率. 在执行正向和逆向 NTT 的过程中, 使用层融合技术 [28] ,
如图 1 所示, 线程以特定步长读取共享内存上的数据到自身寄存器后, 无需再与共享内存交互, 直接基于寄存器完
成多层 NTT 计算, 从而进一步减少访存带来的开销.

1 1 1 1
共享内存 2 2 2 2
1
3 3 3 3 2
数据交换
3
4 4 4 4 4
正/逆 多项 域收缩 5
域扩张 向 NTT 式点 5 5 5 5 6
乘
寄存器 6 6 6 6
7
8
7 7 7 7
寄存器
全局内存 8 8 8 8
共享内存
基于层融合的数据交互方式
图 1 基于伪梅森数不完整 NTT 的素阶数域多项式乘法的内存模式