我正在尝试实现一个素数分解算法，该算法利用GPU/CUDA作为一个宠物项目进行并行化。
我将python与numpy和numba一起用于并行化部分。
我现在的问题是，我很快就达到了64位整数边界，我正在寻找解决方案来解决这个问题。由于numpy/numa只支持高达64位的整数(与python本身的任意大数字相比(，这就是我目前的困境。
从本质上讲，GPU上的部分主要使用模运算和一点迭代。
我发现，通过用较小的除数将模分解为多个运算，我可以在模上使用较大的除数。
示例：
假设我们不能使用大于10^3的数字。
我想在GPU上做以下操作：
1019 % 17 = 16
我可以通过将被除数1019划分为多个任意大小的块来实现这一点，例如：
1019 = 500 + 519
然后分别计算所有块的模，并再次对结果的和取模。
((500 % 17) + (519 % 17)) % 17 = 16
我现在的问题是：有没有类似的运算我可以用更大的除数和商来运算(例如2037 % 1019(？或者更好的方法是，在numpy/numba中使用任意大小的数字而不损失精度？
如果我没有使用正确的数学俚语，请原谅我。
由于基本的全等恒等式规则，使用模可以更有效地减少被除数。事实上：
Assuming:
a ≡ x [d]
b ≡ y [d]
c ≡ z [d]
Then:
a * b + c ≡ x * y + z [d]
如果d很小，这是一个有趣的性质。此外，所有数字都可以分解为两个值的幂和，并且使用模幂运算可以很容易地预先计算2**n模d的余数。
例如：
15428794586587458 ≡ 3592296 * 2**32 + 749035842 [2019]
≡ 495 * 1090 + 975 [2019]
≡ 477 + 975 [2019]
≡ 1452 [2019]
不幸的是，当涉及到除法器时，AFAIK没有简单有效的(即多项式(方法来减少除法器和被除数(尤其是前者(的特殊假设。我认为用这样的约简来求解素数分解会简单得多。假设除数d是一个复数，那么中国余数定理肯定有助于将除法分解成更简单的部分，但如果d是素数，那么AFAIK这是一个难题。
在这种情况下，使用可变精度数字(或简单地使用多个部分的大整数(无疑是最简单的解决方案。一个简单的解决方案是使用二进制搜索，因为a ≡ b [d]等价于求解a = k * d + b。事实上，k可以一次又一次地乘以2，直到k * d大于a，然后可以使用对k的二进制搜索，使得a ≤ k * d < a + d。使用Karatsuba算法可以有效地计算乘法(对于非常大的数字有更快的方法，但对于在您的情况下肯定使用的相当大的数字，这种方法更快(。AFAIK，牛顿方法可以用于存档更快的归约(两者在算法上都很快，但后者收敛得更快(。