Stephenson:Neal:The Confusion:301:decompose such a number into its prime factors (Electricinca)

From the Quicksilver Metaweb.

From a conversation discussing systems for the ordering of a library's contents between Gottfried Wilhelm von Leibniz and Nicolas Fatio de Duillier.

Leibniz's proposal is to assign a different prime number to each possible subject matter. For example:

2	Plato
3	Aristotle
5	Trees
7	Turtles

The extension of such a system allows that if one wished to find a book about Trees by Plato then it would be housed on a shelf numbered 10 which is the product of each individual subject's number. i.e. 2 x 5 = 10.

Fatio points out a flaw for a sufficiently large library with shelves that extend for countless leagues.

Looking at a shelf I might see some number, eight or nine digits long. I would know this to be a composite number, the product of two or more primes. But to decompose such a number into its prime factors is a notoriously difficult and tedious problem. There is a curious asymmetry about this approach...

This same curious asymmetry is the basis for the RSA algorithm used in public key cryptography.

The flaw in the system pointed out by Fatio isn't in my opinion a flaw. Looking at his hypothetical shelf with the impossible large composite number, you need not factor it to discover the contents you merely need to look at the books on the shelf. The converse however allows one to quickly find the appropriate shelf for a specific type of book as the multiplication of primes is relatively trivial.

The problem of factoring large numbers into primes could be avoided by employing an Arithmetic (as opposed to a geometric) system, based on powers of two instead of prime numbers. For, as each natural number can be expressed as a unique product of ascending primes, each natural number can also be expressed as a unique sum of ascending powers of two.

For example:

1	Plato
2	Aristotle
4	Trees
8	Turtles
16	Mercury
32	Cryptography
64	Neal Stephenson

Using this method, a book by Plato about Trees could be found on a shelf numbered 5, which is the sum of each individual subject's number. i.e. 1 + 4 = 5.

While it is difficult to factor very large composite numbers (in fact, many cryptosystems depend entirely on that difficulty), it is trivial to express large numbers as sums of powers of 2 (binary notation).