3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Feb 11 '14 at 15:03
  • $\begingroup$ yes i am allowed to find the reminder as much as i want $\endgroup$ – kirill Feb 11 '14 at 15:04
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Minor point but the primes you have chosen are not in the acceptable range for the problem statement. $\endgroup$ – John Habert Feb 11 '14 at 16:11
  • $\begingroup$ @JohnHabert: Oops, fixed. $\endgroup$ – Nate Eldredge Feb 11 '14 at 16:17
  • $\begingroup$ Could you elaborate about the constructive algorithm, or link some step by step example? $\endgroup$ – kirill Feb 18 '14 at 16:42
  • $\begingroup$ @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). $\endgroup$ – Nate Eldredge Feb 18 '14 at 16:55
  • $\begingroup$ 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 $\endgroup$ – kirill Feb 18 '14 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.