## Paul v. Scientific American

*[Editor’s note: Sent to the editors in question. By some corollary to Skitt’s Law, naturally, I managed to screw up the second set of page references in the copy I sent them. Sigh.]*

In the June 2007 Scientific American article “Breaking Network Logjams”, the sidebar on page 83 claims “Still, when neither `a` nor `b` is 0, both receivers can retrieve the proper messages successfully.” Alas, selecting codes is not quite that easy: `a` and `b` must be relatively prime to 2^{m} (where `m` is the number of bits per message). Only then is

a*X+b*Y=E(modulo 2^{m})

guaranteed to have a unique solution when all variables except either `X` or `Y` are known. `a` and `b` needing to be nonzero is merely a special case of this requirement.

Luckily, since 2^{m} will never have any prime factors besides 2, choosing odd numbers for `a` and `b` guarantees they will be relatively prime to 2^{m}. Although this means that a purely random choice for `a` and `b` will only work 25% of the time, it is trivial to restrict the random choice to only odd numbers to begin with.

The example on pages 82 and 83 in fact demonstrates what happens when `a` and `b` are chosen poorly. In the example, `a` = 3 is a safe choice, but `b` = 20 is poor, since 20 and 32 have a common factor (4). In solving

3 * 21 + 20 *

Y= 23 (modulo 32)

there are four possible values for `Y`: 6, 14, 22, and 30. There is no way to tell which possible value for `Y` corresponds to Ben’s message; as a result, Carl is unable to receive Ben’s message reliably.