gpu上的大整数乘法与加法

Question

我在GPU上开发加密算法。这个算法需要非常大的整数的加法和乘法。这些数字的位长估计为150,000位，或者more.These数有不同的位长。有什么算法可以用来执行这些数字的加法和乘法？请告诉我你的信息。谢谢。

Answer 1

大整数加法比较简单: JackOLantern已经提供了到post的链接。基本上，它只是通过并行前缀和进行进位传播。

对于数据自动化系统上的大整数乘法，我认为有两种方法：

• 将整数转换为RNS (剩余数系统)：然后可以并行地进行乘法和加法(只要RNS基足够大)。当您需要比较数字时，您可以将它们转换为混合基数系统(参见，例如，如何将残数系统转换为混合基数系统？)。最后，您可以使用CRT (中文剩余)将数字转换回位置编号系统。
• 直接使用FFT实现大整数乘法，因为乘法可以看作是序列的非循环卷积(对于FFT，150 that的长度不是很大，但已经给了您一些加速比)。尽管如此，GNU MP切换到FFT乘法例程从1 1Mbit甚至更多。同样，对于通过FFT进行乘法，有两个选项：

1. use floating-point double-precision FFT and encode large-integer bits into mantissa (easier to implement)
2. use the so-called Number-Theoretic transform (FFT over finite field)

​

不管怎么说，这些事情背后有很多理论。你也可以在CUDA中的FFT mul上查看我的论文。但也有很多关于这一课题的研究论文，特别是在密码学领域。