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 2m (where m is the number of bits per message). Only then is

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

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 2m will never have any prime factors besides 2, choosing odd numbers for a and b guarantees they will be relatively prime to 2m. 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.