c 代码:防止模块操作中的超大模块溢出(靠近溢出阈值的模块) [英] c code: prevent overflow in modular operation with huge modules (modules near the overflow treshold)

问题描述

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

In my c code I have to perform a series of recursive modular operations. In particular I have to perform operations like (A*B)modC, with C~2^126, and A,B that, in principle, could be very big numbers (from 0 to 2^128 - 1) ( I work with 128 bit unsigned __int128 variables).
The problem is how to perform the module during the multiplication process. I need this because if the module is performed after the multiplication, I could exceed 2^128 (if A and B are very big) during the multiplication and corrupt the successive modular operation.
So I'd like to perform a multiplication which restart from 0 every time that I pass C (during the multiplication process) instead of every time I pass 2^128 - 1.
How should I do this?

推荐答案

最简单的解决方案是将乘法实现为位循环，每次移位一并添加.通过这种方式，您可以计算每次通过循环的中间结果的模数.

The naive solution is to implement multiplication as a loop over bits, shifting by one and adding each time. This way you can compute the modulus of the interim result each pass through the loop.

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

It requires 128 shifts, 128 additions and 128 modulo operations. If that is too slow for you then some boffin can probably tell you an optimization (but everyone knows you should only consider optimization once you are sure that the simplest solution isn't fast enough).

这篇关于c 代码:防止模块操作中的超大模块溢出(靠近溢出阈值的模块)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！