将 BigInteger 替换为 UInt64 用于素数分解算法，其中 N < 2^63

Question

我有一个很好的解决方案，在VB中实现质因数分解。使用Pollard's Rho和Brent's算法的BigInteger(参见:https://stackoverflow.com/a/31978350/44080)

对于N< 2^63，我认为UInt64应该足够大，并且可能(很多?)更快。

然而，我的UInt64转换在这一行失败:

y = ((y^2) Mod n + c) Mod n 'fails when y^2 > UInt64.Max

将这行改为

y = CULng((CDbl(y^2) Mod n + c) Mod n)

会降低性能，因为类型转换是在循环中进行的。

请问我该如何解决这个问题?

我仍然认为，如果我们能避开上述问题，UInt64的性能将超过BigInteger。

编辑:

我刚刚发现这个:Dirichlet。net数论库，声称有Int128和Int256执行。net BigInteger。

它甚至有几个素数分解的优化算法。可以节省我2天的研究和测试。

Answer 1

如何进行模乘法(计算平方)而不会溢出:

只要模数至少比最大值小一位，解决方案是将数字分成低位和高位两半，然后执行算术零整，有点像小学乘法，先乘以个位数，然后移动和并乘以十位，以此类推，除了"数字"是整数数据类型中可以表示的最大数字的平方根的大小。

考虑使用8位算术计算56 * 37模100的例子，因此中间总数不可能大于或等于256。我们首先表示a = 56 = 3 * 16 + 8和b = 37 = 2 * 16 + 5，(注意16是256的平方根)所以:

a1 = 8
a2 = 3
b1 = 5
b2 = 2

则四个中间产物及其移位为:

p11 = 8 * 5 = 40
p12 = 8 * 2 = 16 > 32 > 64 > 128 (28) > 56
p21 = 3 * 5 = 15 > 30 > 60 > 120 (20) > 40
p22 = 3 * 2 = 6 > 12 > 24 > 48 > 96 > 192 (92) > 184 (84) > 168 (68) > 136 (36)

我们使用的是二进制运算，所以每一个数字在移位的时候都会翻倍，在移动的时候取100的模。两个低半数的乘积不移位，低半数与高半数的乘积移位4次(因为log₂ 16 = 4)，两个高半数的乘积移位8次。然后对中间产品求和，每次中间产品超过m时，再次删除m:

s = 40 + 56 = 96
s = 96 + 40 = 136 (36)
s = 36 + 36 = 72

这就是最终答案:56 * 37 = 2072，也就是72 (mod 100)。

如果m在整数数据类型的最大值的1位以内，事情会变得更混乱;基本答案是将其分成三部分，计算中间产物，然后重新组合。

查看我的博客中Scheme的代码，以及使用稍微不同算法的C解决方案。