December 26, 2005

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
Comments

Monday, December 26, 2005
CrimeWatch

China babus take $35 bn corruption cake

Beijing, December 26 Chinese auditors have uncovered 290 billion yuan (35 billion dollars) in funds illegally spent by government offices in the first 11 months of this year, state media said here today.

The improper spending was found during a nationwide annual audit of 22,000 officials by the National Audit Office, Xinhua news agency said.

Details were not given but previous findings about misspending involved officials using public funds to build apartments for employees or to give themselves bonuses.

About 196 of the officials were disciplined by their superiors or prosecuted in court, the report said, which cited sources with a National Audit Conference that opened in Beijing today.

The annual audits are an attempt by the government to stem a rising tide of corruption, which is tarnishing the Communist party's image and fuelling ordinary people's anger against the government.

Next year, the audit authority plans to scrutinize some of the branch offices of China's biggest commercial banks, the Bank of China, the Bank of Communications and the China Merchants Bank, Xinhua said.

Corruption is endemic in China and has grown during its economic reform period, threatening the legitimacy of the Communist government, the Organisation For Economic Cooperation and Development said earlier.

URL: http://www.financialexpress.com/latest_full_story.php?content_id=112633

Posted by: Jimbo at December 27, 2005 04:40 AM

Wow! this provides me with excellent cocktail party material....and I know that no one will challenge me!

Keep up the good work!

Best Wishes for a Happy Holiday Season & the New Year!

Cheers

Posted by: Lyn at December 28, 2005 06:15 AM
Post a comment









Remember personal info?






Hit preview to see your comment as it would be displayed.