我想在C中用两个整数对另一个（质数）整数（长度大约为50位）取模相乘。
uint64_t x = ...;
uint64_t y = ...;
uint64_t q = ...;
uint64_t z = (x*y) % q;这将产生一个小于q的64位整数，但不幸的是x%q * y%q对于64位类型来说太大了，所以在我计算余数之前它就溢出了。
我想到了一些变通办法：
- 使用gcc的
__uint128_t将违反C标准，并且不能与其他编译器一起工作 - 将变量强制转换为
double或long double，但由于浮点不准确，结果将不正确 - 使用像GMP这样的多精度库是可行的，但是这引入了新的项目依赖性，并且可能带来一些开销
- 为此我自己编写了一个乘法函数，但据我所知，我需要汇编，所以可移植性消失了
有没有其他的选择或者你有什么建议？
编辑：我忘了提一下，一个自己写的解决方案只有在高效的情况下才值得做。例如，做几十个低效的%操作会很糟糕。
2条答案
按热度按时间a9wyjsp71#
当然，您不需要汇编程序来自己实现任意精度的乘法。
有很多著名的算法可以实现这个功能，而且（根据定义）它们可以用C实现。
更多信息请参见Wikipedia。根据我的经验，正确地编写这样的代码可能有点棘手，所以也许您的时间最好花在添加依赖项上。
6mzjoqzu2#
在您的特定情况下，最好将数字分为四个13位部分，然后使用长手法将它们相乘，并对中间结果求模。
代码如下所示：
这将仅需要4次乘法和9次模运算。