math - 找到已知 mod 2^i 的 mod m

Question

我需要找到 的值a mod m。但我没有a直接的价值。我有以下模数值a。
a mod 2 ¹
a mod 2 ²
a mod 2 ³
...
a mod 2 ⁿ

现在我需要找到a mod m可以 在 O(n) 时间内完成的地方吗？m < 2n

Answer 1

如果没有更多信息，它根本无法完成，更不用说在 O(n) 时间内完成了。

首先请注意，您只有一条信息：即 ; 的值a mod 2^n。所有早期的余数都可以a mod 2^n通过归约来计算，因此它们不提供新信息。

然后，例如，如果m是奇数，则 的值a mod 2^n不会告诉您 的值a mod m：中国剩余定理告诉您，对于任何值0 <= b < 2^n和0 <= c < m，您都可以找到和的a值。a mod 2^n = ba mod m = c

如果m是偶数但不是幂，2那么您将获得有关可能性的部分信息a mod m。只有在m幂2小于或等于的情况下，2^n您才能确定（通常通过归约） 的值a mod m。