c - GPU上的大整数乘法和加法

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 8 年前。

Improve this question

我正在 GPU 上开发一种加密算法。该算法需要非常非常大的整数的加法和乘法。这些数字的位长度估计为 150,000 位或更多。这些数字具有不同的位长度。可以使用什么算法来执行这些数字的加法和乘法？请给我你的信息。谢谢。

Answer 1

大整数加法相对简单:JackOLantern 已经提供了该帖子的链接。基本上它只是通过并行前缀和进行进位传播。

对于 CUDA 上的大整数乘法，我想到了两种方法:

• 将整数转换为 RNS(残数系统):然后可以并行执行乘法和加法(只要 RNS 基数足够大)。每当您需要比较数字时，您可以将它们转换为混合基数系统(例如，参见 How to Convert from a Residual Number System to a Mixed Radix System? )。最后，您可以使用CRT(中文余数)将数字转换回位制数字

• 直接使用 FFT 实现大整数乘法，因为乘法可以被视为序列的非循环卷积(150Kbits 长度对于 FFT 来说并不是那么多，但已经可以给你带来一些加速)。 GNU MP 仍然从 1Mbit 甚至更多开始切换到 FFT 乘法例程。同样，对于通过 FFT 进行乘法，有两种选择:

  1. 使用浮点 double FFT，将大整数位编码为尾数(更容易实现)

  2. 使用所谓的数论变换(有限域上的 FFT)

无论如何，这些事情背后都有很多理论。您也可以查看我的论文FFT mul in CUDA 。但也有很多关于这个主题的研究论文，特别是在密码学领域。