Bignum 库，慢素数生成器
我正在开发一个bignum库： http://pastebin.com/nFgF3zjW 我实现了 Miller-Rabin 算法 (isprime())，但与 OpenSSL 的 BN_is_prime_fasttest 等相比，它非常慢。
我尝试进行分析，执行最多的函数是 bn_shr_atomic 和 bn_cmp 。 知道如何才能让它更快吗？
I am developing a bignum library: http://pastebin.com/nFgF3zjW
I implemented the Miller-Rabin algorithm (isprime()), but it is extremely slow, compared to for example OpenSSL's BN_is_prime_fasttest.
I tried profiling and the functions that are executed the most are bn_shr_atomic and bn_cmp.
Any idea how I can make this faster?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
GNU 多精度算术库实现了 Miller-Rabin。它的文档位于此处：
http://gmplib.org/manual /Number-Theoretic-Functions.html#Number-Theoretic-Functions
我建议检查它们的实现以获取加速计算的指针。然而，任意精度算术本质上会比处理适合寄存器的数字慢。
编辑：
所使用的算法和结果概率的质量之间也存在权衡。也就是说，我不确定 OpenSSL 使用什么测试。
The GNU Multiple Precision Arithmetic library implements Miller-Rabin. It's documentation is located here:
http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions
I would suggest examining their implementation for pointers on speeding up your computation. However, arbitrary precision arithmetic is inherently going to be slower than working with numbers that fit in registers.
Edit:
There is also a trade-off between the algorithm used and the quality of the resulting probability. That said, I'm not sure what test OpenSSL uses.
大猜测：如果你真的想使用自己的库，我会首先用长除法替换除法算法。
为了验证我的猜测：您的部门内循环中有 cmp 和 shr，这些调用是您个人资料中的主要贡献者还是来自其他地方？一般来说，当您分析时，您应该首先查看贡献较大的高级函数，更改算法通常比调整低级函数更有益。
Big guess: If you really want to use your own library, I'd first replace the division algorithm by the long division.
To validate my guess: you have cmp and shr in the inner loop of your divison, are those calls the major contributor in your profile or do they come from somewhere else? In general, when you profile you should first look at higher level functions which are big contributor, changing algorithms there is usually more benefical than tuning low level functions.