c - Bignum 库，慢素数生成器

Question

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

我尝试进行分析，执行最多的函数是 bn_shr_atomic 和 bn_cmp 。知道如何才能让它更快吗？

Answer 1

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

http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions

我建议检查他们的实现以获取加速计算的指针。然而，任意精度算术本质上会比处理适合寄存器的数字慢。

编辑:

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