模运算的性质

Question

我计算求和S = (a*x + b*y + c) % n。是的，它看起来像一个二次方程，但它不是，因为x和y有一些性质，必须使用一些递归关系来计算。因为这个和甚至超过了unsigned long long的极限我想知道如何用模运算的性质来计算这个和，这些性质允许写出这样的和(我这么说是因为我不太记得那些性质是怎么写的)(a*x)%N + (b*y)%N + c%N，从而避免超过unsigned long long的极限。

提前感谢您的关心!:)

Answer 1

a % N = x表示对于某些整数0 <= x < N和m: m * N + x = a。

你可以简单地推断如果a % N = x和b % N = y则

(a + b) % N =
= (m * N + x + l * N + y) % N =
= ((m + l) * N + x + y) % N =
= (x + y) % N =
= (a % N + b % N) % N.

我们知道0 < x + y < 2N，这就是为什么你需要保留余数计算。这表明可以拆分总和并分别计算余数，然后将它们相加，但不要忘记获得总和的余数。

乘法:

(a * b) % N =
= ((m * N + x) * (l * N + y)) % N =
= ((m * l + x * l + m * y) * N + x * y) % N =
= (x * y) % N =
= ((a % N) * (b % N)) % N.

因此，您也可以对产品做同样的操作。

这些属性可以简单地在更一般的设置中使用一些抽象代数推导出来(余数形成一个因子环Z/nZ)。

Answer 2

如果需要的话，你还可以更进一步:

S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N

Answer 3

您可以按照您的建议将模数应用于总和的每一项;但即便如此，在它们相加之后，你必须再次应用模数来得到你的最终结果。

Answer 4

这个怎么样:

   int x = (7 + 7 + 7) % 10;
   int y = (7 % 10 + 7 % 10 + 7 % 10) % 10;

Answer 5

你没记错。你给出的公式，每个和式取%N是正确的。这就是我要用的。对于每一个部分和(和总数)，你也应该再次使用%N，因为加法的结果仍然可能大于N。但要注意，这只适用于你的大小限制至少是N的两倍。如果不是这种情况，它会变得非常糟糕。

对于以下%N的部分和运算，你不必执行完全除法，检查> N，如果大于N，只需减去N就足够了

Answer 6

不仅可以在开始计算之前减少所有变量mod n，还可以编写自己的mod-mul，通过使用shift-and-add方法来计算a*x mod n，并在每一步减少结果mod n。这样你的中间计算只需要比n多一个比特。一旦这些乘积被计算出来，你可以将它们两两相加，并在每次相加后减少mod n，这也不需要超过n范围的1比特。

在我对这个问题的回答中有一个模块化乘法的python实现。转换成C语言应该很简单。