"Decimal CRC"
				~~~~~~~~~~~~~

Goal:  send a sequence of decimal digits (beginning with a nonzero digit) as an
expanded sequence capable of detecting a burst error of up to B decimal digits.

Sender:
(1) Sender and receiver agree on prime number P between 10^B and 10^(B+1).
(2) Given message M, let R = (10^(B+1) * M) % P.
(3) Send encoded message S = 10^(B+1) * M - R.

Receiver:
(1) On receipt of encoded message S', test whether P divides S'.
(2) If not, there has been an error; ask Sender to re-transmit.
(3) If so, extract M by dividing S' + (P-1) by 10^(B+1), ignoring remainder.

Concretely, suppose B = 3, P = 1009 and M = 348722.

Sender computes R = 974, the remainder of 3487220000 divided by 1009, and sends
3487219026, the difference of 3487220000 and 974.

If there is no error, Receiver receives 3487219026; sees it is divisible by
1009; and recovers the message by dividing 3487220034 (= 3487219026 + 1008) by
10000 and ignoring the remainder, giving 348722.

Suppose now 3 consecutive digits of the encoding are changed, so that Receiver
receives 3487645026.  On dividing this by 1009, the remainder is 202, so
Receiver requests a re-transmit.

Why should this work?  Suppose that Sender sends S and Receiver receives S'.
We know that 10^(B+1) * M = Q * P + R for some integer Q, where R is the
remainder on dividing 10^(B+1) * M by P.  Then S = 10^(B+1) * M - R = Q * P, a
multiple of P.  Thus if there is no error, S' is a multiple of P.  Moreover,
since R < P < 10^(B+1), We have 0 <= (P-1) - R < 10^(B+1) and, ignoring the
remainder, S' + (P-1) = 10^(B+1) * M + ((P-1) - R) divided by 10^(B+1) is M.

If there is a burst error of at most B digits, then S' - S = E * 10^K for some
integer E with |E| < 10^B and some nonnegative integer K.  Suppose that S' is
divisible by P so that the error is not detected.  Since S is also divisible by
P, so is S' - S = E * 10^K.  But |E| < 10^B < P, and E must be divisible by P
since P is prime.  Thus, we must have E = 0; that is, there was no error, and
S' = S, a contradiction.

Why don't we implement this?  Integer division is an expensive operation.
Actual CRC implementations depend on division of polynomials with coefficients
in GF(2), where the division can be implemented using shift and XOR.

								CS-323-11/14/18