如何快速执行(a * b) % c，其中a,b,c很长，而且通常很大

Question

所有值(a, b, c)都是ulongs，并且可以变得非常大(有时也会达到ulong.Max)

如何使(a * b) % c快速执行。我对模乘法做了大量的研究，但是没有找到任何有用的东西。那么最快的计算方法是什么呢?我知道我可以使用BigInteger，但BigInteger是可怕的慢，所以我不打算使用它。

另一个可以为我工作的是highbits和lowbits % c(因为我可以使用Math.BigMul)。但是我还没有找到任何适用于64位的东西(只有63位)。

Answer 1

下面是一个使用Math.BigMul方法(. NET 5及更高版本)，decimal数据类型:

/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
ulong high = Math.BigMul(a, b, out var low);
if (high == 0) return low % modulo;
if (high <= 0xFFFFFFFF) return (ulong)(((decimal)a * b) % modulo);
decimal remainder = high;
remainder *= 0x100000000;
remainder += low >> 32;
remainder %= modulo;
remainder *= 0x100000000;
remainder += low & 0xFFFFFFFF;
remainder %= modulo;
Debug.Assert((BigInteger)remainder == ((BigInteger)a * b) % modulo); // Validation
return (ulong)remainder;
}

这个实现分两步执行操作，以克服decimal类型的96位限制。它几乎比使用BigInteger类型快2倍，而且它不分配内存。如果两个数的乘积符合十进制范围，则一步得到结果。

对于不依赖于Math.BigMul方法(源代码)的类似但稍慢的实现，您可以查看此答案的第4版。

---

更新:如果可以使用本地UInt128类型，(a * b) % c操作甚至可以更快。不幸的是，这种类型并不存在。如果你喜欢冒险，你可以使用Rick Sladkey的Dirichlet . net数论库(MIT许可)，其中包括这种类型(以及Int128)。你可以下载UInt128.cs代码文件，并将其包含在你的项目中。然后你可以这样做:

public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
return (new Dirichlet.Numerics.UInt128(a) * b) % modulo;
}

它比我PC上的BigInteger快2.5倍。

这个代码文件有大约2.700行代码。如果您只对(a * b) % c功能感兴趣，如果您认为值得的话，您可以将其精简到150行左右。

Answer 2

答案来自https://stackoverflow.com/a/18680280/14133865

public static ulong ModMul(ulong a, ulong b, ulong modulus)
{
ulong result = 0UL;
if (b >= modulus)
{
if (modulus > 0x7FFFFFFFFFFFFFFF)
{
b -= modulus;
}
else
{
b %= modulus;
}
}
while (a != 0UL)
{
if ((a & 1UL) != 0UL)
{
if (b >= modulus - result)
{
result -= modulus;
}
result += b;
}
a >>= 1;
ulong temp = b;
if (b >= modulus - b)
{
temp -= modulus;
}
b += temp;
}
return result;
}