c - Bignum 库，慢速生成器

Question

我正在开发一个 bignum 库：http://pastebin.com/nFgF3zjW 我实现了 Miller-Rabin 算法 ( isprime())，但与 OpenSSL 的 BN_is_prime_fasttest 相比，它非常慢。

我尝试了分析，执行最多的功能是bn_shr_atomic和bn_cmp. 知道如何使这更快吗？

score 1 · Accepted Answer

GNU 多精度算术库实现了 Miller-Rabin。它的文档位于此处：

我建议检查他们的实现以获取有关加快计算速度的指针。但是，任意精度算术本质上会比使用适合寄存器的数字要慢。

编辑：

在所使用的算法和结果概率的质量之间也有一个权衡。也就是说，我不确定 OpenSSL 使用什么测试。

score 0 · Accepted Answer

大猜测：如果您真的想使用自己的库，我首先将除法算法替换为长除法。

为了验证我的猜测：您在部门的内部循环中有 cmp 和 shr，这些呼叫是您个人资料中的主要贡献者还是来自其他地方？通常，当您进行概要分析时，您应该首先查看贡献较大的高级函数，更改算法通常比调整低级函数更有益。

2 回答 2