Reputation: 5297
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 21
a mod 22
a mod 23
...
a mod 2n
Now I need to find a mod m
where m < 2
n
Can this be done in O(n) time ?
Upvotes: 0
Views: 74
Reputation: 30601
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
.
Upvotes: 3