          http://www.wwp.brown.edu/vol02num03/toc023.html

Brown University Women Writers Project Newsletter article “Keying NAMEs: the WWP Approach”

Appendix: Proofs

A 12-character expanded name is coded into a number base 27, call it N. N is of the form

N = a_{11} × 27^{11} + ⋯ + a_{i} × 27^{i} + ⋯ + a_{1} × 27 + a_{0}

where the a_{i} coefficients are all in the range [0, 1, …, 26]. We must show that common errors always change the remainder when N is divided by 29. We consider single-character errors and transpositions.

single character error Suppose a single character of N is in error, i.e., say a_{i} has been mistakenly entered as b_{i}, so that

N′ = a_{11} × 27^{11} + ⋯ + b_{i} × 27^{i} + ⋯ + a_{1} × 27 + a_{0}

Then

N − N′ = (a_{i} − b_{i}) × 27^{i}

We note that 29 cannot divide a_{i} − b_{i}, which is at most 26 (range from −26 to +26); nor, since it is a prime, can 29 divide 27^{i}, which has 3 as its only prime factor. Therefore it does not divide N − N′, and so N′ ≠ N mod 29.

transpositions Suppose there is a transposition of two letters, corresponding to a transposition of two coefficients, a_{i} and a_{j}, where i > j. Now N − N′ will be of the form

N − N′ = (a_{i} − a_{j}) × 27^{i} + (a_{j} − a_{i}) × 27^{j}
= (a_{i} − a_{j}) × 27^{i} − (a_{i} − a_{j}) × 27^{j}
= (a_{i} − a_{j}) × 27^{j} × (27^{i−j} − 1)

As for “single character error”, above, 29 cannot divide either of the first two factors. We must examine whether 29 can divide the third, i.e., a number of the form 27^{k} − 1, where k is an integer in the range 1–11. This is a matter of simply testing all 11 values of k, one at a time, and none of these is divisible by 29. (Actually this is the case for any k in the range 1–27.) So once again, the error results in an N′ that has a different remainder from N, mod 29. (And, indeed, the method would work for strings up to 28 characters.)

other random errors It is possible that multiple errors would compensate for each other, giving a false validity check. The frequency of false checks, in cases of completely random garble, would be about 1/29 = 3.4%. Thus this method detects over 96% of errors, including all of the most common ones.

Copyright ◯^{c} 1997 Syd Bauman and Brown University Women Writers Project.