基于FFT的超大整数高精度乘法电路实现咨询

核心方案：用NTT替代浮点FFT #

浮点FFT的误差源于浮点数精度限制，而数论变换（NTT） 是在有限域$\mathbb{Z}/p\mathbb{Z}$（$p$为素数）上的离散傅里叶变换，所有运算均为整数操作，完全满足无浮点数、精确计算的要求，且几乎不需要非整数运算。

关键设计步骤 #

1. 选取适配的NTT素数模数 #

需满足两个核心条件：

• 模数$p$必须是形如$c \cdot 2^k + 1$的素数（广义费马素数），这样存在足够大的$2^{k$阶本原根，能覆盖数兆字节级整数的二进制长度（比如选$p=998244353=119\times2}{23}+1$，或更大的$p=2^{64}-2{32}+1$）。
• 模数$p$要大于整数分段后的单段最大值，避免运算溢出；若单模数无法覆盖最终乘积范围，可采用多模数NTT，后续用中国剩余定理（CRT）合并结果。

2. 超大整数的分段转换 #

将数兆字节的超大整数按模数$p$的范围拆分为多个小整数段，比如每个段对应$m$位二进制，满足$2^m < p$，把原整数转化为分段多项式：

例：整数$N = n_0 + n_1 \cdot B + n_2 \cdot B^2 + ... + n_{L-1} \cdot B^{{L-1}$，其中$B=2}m$为基数，每个$n_i \in [0, B-1]$，对应多项式$P(x) = n_0 + n_1 x + n_2 x^2 + ... + n_{L-1} x^{L-1}$。

整数乘法等价于两个多项式的乘积，最终再将多项式系数合并为整数（处理进位）。

3. NTT的纯整数电路实现 #

NTT的所有运算均为有限域内的整数操作：

• 加法/减法：用整数寄存器直接实现，结果对$p$取模（若结果为负，加$p$转为正整数）。
• 乘法：用整数乘法器实现，结果对$p$取模——可通过预计算模数的逆元，用乘法替代除法取模，完全规避非整数运算。
• 本原根幂次运算：预计算所有需要的本原根幂次并存储为整数常量，运算时直接与寄存器值相乘取模。

4. 逆NTT与结果合并 #

完成多项式乘积的NTT变换后，执行逆NTT得到乘积多项式的系数，再：

• 对每个系数做进位处理，将分段值合并为最终的超大整数。
• 若采用多模数NTT，用中国剩余定理将不同模数下的结果合并为真实整数，所有操作均为整数运算。

优化要点（最小化非整数依赖） #

• 所有取模操作通过整数乘法+减法实现，避免除法：利用模$p$的性质预计算逆元，结合二进制补码电路的移位+减法优化取模流程。
• 预存储所有本原根幂次，无需实时计算非整数。
• 采用迭代型NTT结构，复用乘法器和加法器，减少硬件资源开销。

内容的提问来源于stack exchange，提问作者Adar Maori