如何快速判定两大整数的整除性？

gxqcn

看 B|A 是否成立，一般的做法是计算出 A%B（余数），看结果是否为零。 而判定是否可整除，应该是比求余数更弱的问题，不知可有哪些快速算法。 注：可假设大整数 A、B 分别有 2n、n 位。

wayne

1# gxqcn 不知道大整数是怎么存储的

G-Spider

看看有没有帮助。

gxqcn

3# G-Spider 这篇似乎是研究十进制的，且为普通整数的，帮助不大。

gxqcn

1# gxqcn 不知道大整数是怎么存储的 wayne 发表于 2011-10-24 10:26

把大整数用β进制表达，用一个数组依次记录其各“位”上的值。

wayne

个人感觉应该没什么特别好的一般方法吧。

wayne

我们可以构造一个分段折算的方法。 假设我们针对较小的那个数B，能找出x ，使得 B*x=9999...999（k个9） 那么，我们就可以把A按k个数字分段， 加起来，这个折算的数就小多了 。。。

gxqcn

上面的那个 x 是容易计算的， 对于任意大的A，虽可快速计算 A mod (B*x)，（其实，这里的B*x一般也达到了2n位） 但无法快速得到 A mod B 的精确结果， 因为 A mod B = (A mod (B*x)) mod B，即：无法跨越第二个求余运算。

wayne

8# gxqcn

gxqcn

上面的那个 x 是容易计算的， 对于任意大的A，虽可快速计算 A mod (B*x)，（其实，这里的B*x一般也达到了2n位） 但无法快速得到 A mod B 的精确结果， 因为 A mod B = (A mod (B*x)) mod B，即：无法跨越第二个求 ... gxqcn 发表于 2011-10-24 19:51

上面第一句话（红色标记的）说错了， 我当时只以为是简单求关于10^k的数论倒数，实际上是不够的。 要找到一个恰当的k，使(10^k-1)或(2^k-1)能被B整除， 可能代价非常大，因为需要的k可能非常非常大， 因为对于每个k，(10^k-1)或(2^k-1)素因子数目是有限的，很难保证恰含有大整数B。