Hacker News new | past | comments | ask | show | jobs | submit login

Here's the long answer to the question: what could anyone learn from rearranging the digits of an integer?

First off, it's helpful to know that the integers (denoted {Z}) are the canonical example of what's called ring structure, which basically means + and * work normally, but you aren't guaranteed clean division. Since they're simple, mathematicians sometimes use {Z} as a stand-in for more persnickety structures in the same way they use n-dimensional Euclidean space as a proxy for thinking about infinite-dimensional vector spaces. Articles like this one usually get written when an algebraist or number theorist publishes an epic proof, and the only way to make it comprehensible to a lay audience is to project it down into toy examples in a simple space. That's kind of a "trust me" answer by itself, of course. So without further ado, the math:

There are two notable things about rings. You can make polynomials with + and * in them, and division generally leaves you with remainders. Remainders are okay, though, because they let you define new rings. {Z mod 12 Z}, for example, is shorthand for "integers mod 12," or more formally, "map the integers to a new space where all the multiples of 12 get sent to zero," so {1, 2, ..., 11 } act normal, 12 is actually zero, 13=12+1=0+1=1 and so on.

It turns out that this is all you need to represent numbers in place-value notation. A number N in base r has a representation of n digits:

N = (A_n)(r^n) + ... + (A_2)(r^2) + (A_1)r + A_0

which is just a polynomial whose coefficients are members of the ring {Z mod r*Z}. If you map that back to the integers, plug in the actual value of r, and crunch the numbers, you get your original value of N back.

So, "rearranging the digits of an integer" is actually "permuting the coefficients of polynomials with coefficients mod r."

Now, suppose you have an email message that's 12000 characters long. You can think of that message as the polynomial representation, modulo 256, of a really big number. Mapping that number into different modular spaces, or permuting the coefficients of its various representations so that you can get it back later ("encrypting the message") forms the basis of the field of cryptography, which in turn is closely related to information theory and the theory of ergodic processes, etc, etc, etc.

For more details, you might start with:

http://www.amazon.com/Applied-Cryptography-Protocols-Algorit...

http://www.inference.phy.cam.ac.uk/mackay/itila/book.html




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: