Finding a mod m where a mod 2^i are known

Question

I need to find the value of a mod m. But I dont have the value of a directly. I have the following modulus values of a.
a mod 2¹
a mod 2²
a mod 2³
...
a mod 2ⁿ

Now I need to find a mod m where m < 2n
Can this be done in O(n) time ?

Answer 1

It can't be done at all without more information, let alone in O(n) time.

Note first that you only have one piece of information: namely, the value of a mod 2^n; all of the earlier remainders can be computed from a mod 2^n by reduction, so they don't provide new information.

And then if, for example, m is odd, the value of a mod 2^n tells you exactly nothing about the value of a mod m: the Chinese Remainder Theorem tells you that for any values 0 <= b < 2^n and 0 <= c < m, you can find a value of a such that a mod 2^n = b and a mod m = c.

If m is even but not a power of 2 then you get partial information about the possibilities for a mod m. Only in the case that m is a power of 2 less than or equal to 2^n can you determine (trivially, by reduction) the value of a mod m.