Financial Cryptography

How the Chinese avoided insider fraud for over a millenium - The Chinese Remainder Theorem

Guest poster Daniel Nagy writes me a human readable explanation of the Chinese Remainder Theorem. That's too valuable a thing to go unposted:

> > Yes, I can agree with that. Yet, it is important to formalize the
> > methodology. (e.g. the Chinese Remainder Theorem was used in ancient China
> > on the basis of experience for more than a millenium before it was exactly
> > formulated and proven.)
>
> Ha! I didn't know that. Yes.....

Hmm. The Chinese Number Theorem was the first use of number theory in security. The Chinese, unlike people in India, did not have a place value system, and did not have floating-point notation, like Babylonians/Greeks either.

However, they did trade in large quantities of stuff (bricks, pottery, etc.). When they shipped a large number of something to some other place, they would write down the remainders of several counts done in modular arithmetic, as divided by a number of small, relative prime numbers. E.g. 1,2,3,4,5,6,7, 1,2,3,4,5,6,7, 1,2,3,4,5,6,7, 1,2 would leave 2 as the remainder for 23 divided by 7. This could be done several times with different primes, like 13, 17, etc,etc.

Now, if all the remainders from the several counts matched, the total number must have matched as well and nothing was stolen. Since addition and subtraction work in this modular arithmetic, this was a very convenient way of accounting for large quantities. This method has the rather stunning benefit that the actual counting can be done by unskilled people, who are only able to count up to a small number.

The only drawback (when compared to place-value system used in India and later in the whole world) is that it does not preserve ordering: finding out which quantity is bigger and which one is smaller is difficult.

Written records (actually, archived letters accompanying shipments) with such counts have been found from as early as the third century A.D. The exact formulation was given by Qin Jiushao in his commentary to the classic book called Mathematics in Nine Chapters (or something like that -- my notes on number theory are in Hungarian), which (the commentary, not the book) was written in 1247 A.D. Nine Chapters is a classic text in Chinese math, similar to Elements by Euclid.

The statement of the theorem is that up to the product of all the moduli, the remainders are unique. Also, Qin Jiushao provided an algorithm for finding the number given the remainders. In his original example, he would make his two disciples measure the distance between his home and a river by holding hands and stepping together, one counting 23, the other counting 17. When they tell the results to their master, he can figure out the distance of three hundred-something steps.

And perhaps as a humorous footnote, consider this: the Chinese managed to get away with using this unproven mathematics in a security system for a millenium or so...

--
Daniel

Addendum: Nick comments and also points at a more mathematical treatment.

Posted by iang at December 26, 2005 11:56 PM | TrackBack