# Deduce the value of a number by only apply modulo operation

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?

• Are you allowed to find U mod N for several different values of N? Then read about the Chinese remainder theorem. I think three different N should suffice. Feb 11, 2014 at 15:03
• yes i am allowed to find the reminder as much as i want Feb 11, 2014 at 15:04

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.$$

• Minor point but the primes you have chosen are not in the acceptable range for the problem statement. Feb 11, 2014 at 16:11
• @JohnHabert: Oops, fixed. Feb 11, 2014 at 16:17
• Could you elaborate about the constructive algorithm, or link some step by step example? Feb 18, 2014 at 16:42
• @kirill: I don't really want to rewrite Wikipedia. But if you have questions after reading what they wrote, you could ask them here (as a new question). Feb 18, 2014 at 16:55
• well, the example on Wikipdia isn't that clear (at least for me). But I found a great video about it here: youtube.com/watch?v=Y5RcMWiUyyE Feb 18, 2014 at 17:01