Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
For an unknown 16 bit number U, an N (8 bit) modulo operation can applied, which results in a known 8 bit number R. The value N must be: 128 >= N >= 255. How do I find U, or at least as much as I can?
The first 7 bytes can be obtained by U mod (2^7) => U AND (2^7).
I thought about doing the same trick with ternary base and find the overlaps. but 5 trit (tribary bits) number can overflow the 8 bit result.
Is there some known trick for that?
To elaborate on my comment: the "known trick" is the Chinese remainder theorem, which says that if $n_1, \dots, n_k$ are pairwise coprime, then given the values of $x \bmod n_1, x \bmod n_2, \dots, x \bmod n_k$, you can recover the value of $x \bmod N$, where $N = n_1 n_2 \cdots n_k$.
In this case, it is sufficient to choose $n_1, \dots, n_k$ such that $N \ge 2^{16}$. The simplest way to guarantee them to be coprime is to choose primes, so for instance, 131, 137, and 139 would do the job.
The Wikipedia article linked above describes some methods for actually finding the solution. Using their "constructive algorithm", I find that we get
$$x = \big(1923343(x \bmod 131) + 1037913(x \bmod 137) + 2028011(x \bmod 139)\big)\bmod 2494633.$$
