GeekSpeak: CRC's

Okay, here's part two of the introduction to checksums, as recently learned by this novice. The concept of a Cyclic Redundancy Check is derived from polynomial math. The idea is this: Take your file or a block of data in binary notation and convert it into a polynomial with coefficients of either one or zero. Ex, if your message was 1101:

1101 --> (1)x^3 + (1)x^2 + (0)x^1 + (1)x^0 --> x^3 + x^2 + 1

Do the same for some carefully chosen "key," Ex:

101 --> x^2 + 1

Multiply the message by x raised to the degree of the key polynomial (in this case, the degree of the key is 2). Ex:

(x^3 + x^2 + 1) * x^2 = x^5 + x^4 + x^2

Divide the result by the key. Ex:

(x^5 + x^4 + x^2) / (x^2 + 1) = x^3 + x^2 + x, R = x

The Remainder is the CRC. Convert this back into bits, Ex:

x --> (0)x^3 + (0)x^2 + (1)x + (0)x^0 --> 0010

Once you send the message, the computer at the receiving end can perform the same operation. If the CRC's are the same, then it is very likely your message was received without error.
All of this math is performed "modulo 2," which basically means that odd coefficients become 1, odd negative coefficients become -1, and even coefficients become 0. Ex:

4x^2 + 3x - 1 --> x + 1

Also, it is imperative that a "good" key is chosen. Really smart mathemeticians have figured out which keys work best. Generally speaking, the longer it is, the more error-proof it is. As an example, a very common CRC key is called "CRC-32". It's polynomial is:

x^31 + x^30 + x^26 + x^25 + x^24 + x^18 + x^15 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1

As we would presume, computers can peform these operations in a more efficient manner than trying to do complicated polynomial math, but as other people have covered this well, I won't go into that here.

Anytime you use the internet, these kinds of operations are going on in the background without you even knowing it. Be thankful that people a lot smarter than you or I (well, at least I) have gone to the effort to figure all this stuff out for us!