c - c 代码：防止在具有巨大模块的模块化操作中溢出（接近溢出阈值的模块）

Question

在我的 c 代码中，我必须执行一系列递归模块化操作。特别是我必须使用 C~2^126 执行 (A*B)modC 之类的操作，而 A,B 原则上可能是非常大的数字（从 0 到 2^128 - 1）（我与128 位 unsigned __int128变量）。
问题是如何在乘法过程中执行模块。我需要这个，因为如果在乘法之后执行模块，我可能会在乘法期间超过 2^128（如果 A 和 B 非常大）并破坏连续的模运算。
所以我想执行一个乘法，每次通过 C（在乘法过程中）而不是每次通过 2^128 - 1 时从 0 重新开始。
我应该怎么做？

Answer 1

天真的解决方案是将乘法实现为位循环，每次移位并加法。这样，您可以计算每次通过循环的中间结果的模数。

它需要 128 次移位、128 次加法和 128 次模运算。如果这对你来说太慢了，那么一些博芬可能会告诉你一个优化（但每个人都知道你应该只在确定最简单的解决方案不够快时才考虑优化）。