对于 N < 2^63 的质因数分解算法，用 UInt64 替换 BigInteger
Replacing BigInteger with UInt64 for Prime factorization algorithms where N < 2^63
我有一个很好的解决方案，用于在 VB.Net 中使用 BigInteger 使用 Pollard's Rho and Brent's algorithms (see: )
实现素因数分解
对于 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 它声称拥有 Int128 和 Int256，其性能优于 .Net BigInteger。
它甚至有几个优化的质数分解算法。本可以节省我 2 天的研究和测试时间。
如何在不溢出的情况下执行mod元乘法（计算平方）：
只要modulus至少比最大值小一位，解决办法就是把数字分成低位和高位两半，然后一点一点地进行运算，有点像就像小学乘法，你乘以个位数，然后移动总和并乘以十位数，等等，除了“位数”是可以表示的最大数的平方根的大小整数数据类型。
考虑使用 8 位算术计算 56 * 37 modulo 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)
我们使用的是二进制算法，因此每个数字在移位时都会加倍，我们将其取 modulo 100。两个低半数的乘积不移位，一个低半数和高半数的乘积移位 4 次（因为 log2 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 在整数数据类型的最大值的一位以内，事情会变得更加混乱；基本答案是分成三部分，计算中间产品，然后重新组合。
请参阅 my blog 了解 Scheme 中的代码，以及使用稍微不同算法的 C 中贡献的解决方案。
我有一个很好的解决方案，用于在 VB.Net 中使用 BigInteger 使用 Pollard's Rho and Brent's algorithms (see:
对于 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 它声称拥有 Int128 和 Int256，其性能优于 .Net BigInteger。
它甚至有几个优化的质数分解算法。本可以节省我 2 天的研究和测试时间。
如何在不溢出的情况下执行mod元乘法（计算平方）：
只要modulus至少比最大值小一位，解决办法就是把数字分成低位和高位两半，然后一点一点地进行运算，有点像就像小学乘法，你乘以个位数，然后移动总和并乘以十位数，等等，除了“位数”是可以表示的最大数的平方根的大小整数数据类型。
考虑使用 8 位算术计算 56 * 37 modulo 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)
我们使用的是二进制算法，因此每个数字在移位时都会加倍，我们将其取 modulo 100。两个低半数的乘积不移位，一个低半数和高半数的乘积移位 4 次（因为 log2 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 在整数数据类型的最大值的一位以内，事情会变得更加混乱；基本答案是分成三部分，计算中间产品，然后重新组合。
请参阅 my blog 了解 Scheme 中的代码，以及使用稍微不同算法的 C 中贡献的解决方案。