.net - 对于 N < 2^63 的质因数分解算法，用 UInt64 替换 BigInteger

Question

我有一个很好的解决方案，用于在 VB.Net 中使用 BigInteger 实现质因数分解，同时使用 Pollard's Rho and Brent's algorithms (参见: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 Number Theory Library它声称拥有优于 .Net BigInteger 的 Int128 和 Int256。

它甚至有几个针对素数分解的优化算法。本可以为我节省 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)，两个高位的乘积-half 数字移位 8 次。然后对中间乘积求和，每次中间和超过 m 时再次删除 m:

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

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

如果 m 与整数数据类型的最大值相差不到一位，事情就会变得更加困惑；基本的答案是分成三部分，计算中间产品，然后重新组合。

参见 my blog对于 Scheme 中的代码，以及使用稍微不同的算法的 C 中贡献的解决方案。