计算功率（a，b）％n其中b和n是大的Uint64_t
我正在玩 https://en.wikipedia.org/wiki/ Miller％E2％80％93Rabin_primality_test
我想测试uint64_t是否是PRIME。为此，我需要计算pow（a，b）％n其中a＆lt; = 37但b和n n 可以是大uint64_t值。我知道我可以在每个步骤中使用goRithm进行pow（a，b）。但这仍然留下2个有问题的操作：（x * x）％n和（x * a）％n。
我想知道，是否有比将所有物品分成低和高32位的更好的东西，并在其余部分进行长时间的乘法和长距离的划分。
PS：不要以为有128位整数类型
I'm playing around with https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
I want to test if a uint64_t is prime or not. For that I need to compute pow(a, b) % n where a <= 37 but b and n can be large uint64_t values. I know I can compute pow(a, b) with the square-and-multiply algorithm doing % n in every step. But that still leaves 2 problematic operations: (x * x) % n and (x * a) % n.
I wonder if there is something better than splitting everything into low and high 32bit and doing long multiplication and long division for the remainder.
PS: don't assume there is a 128bit integer type
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论