[fc-discuss] Financial Cryptography Update: How the Chinese avoided insider fraud for over a millenium - The Chinese Remainder Theorem

[iang@iang.org]

 Financial Cryptography Update: How the Chinese avoided insider fraud for over a millenium - The Chinese Remainder Theorem 

                           December 26, 2005


------------------------------------------------------------------------

https://www.financialcryptography.com/mt/archives/000623.html



------------------------------------------------------------------------

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


-- 
Powered by Movable Type
Version 2.64
http://www.movabletype.org/