Answer by none for Unexpected applications of the fact that nth degree polynomimals are determined by n+1 points

2012-01-07T05:17:13Z

The Reed-Solomon code. A simple example--you have 45gb of data to back up on ten DVD's, but you're worried some discs might get damaged, so you want some redundancy. Erasure codes to the rescue: write out the 10 discs, and also for each byte position on a disc, fit a 9th degree Lagrange polynomial over GF(256) through the byte values across the discs. So, for example, polynomial #23 would go through $(1,b_{1,23}),(2,b_{2,23}),\dots,(10,b_{10,23})$ where $b_{d,n}$ is the data at byte #n of disc #d. Then you can start burning more discs at additional points on the polynomials, e.g. disc #15's data at byte 23 would be $b_{15,23}$ computed from the interpolation polynomial (you can do the finite field arithmetic with a table of "logarithms" and "antilogarithms" for efficiency, but that's a side issue). Now if you make 5 spare discs, you can reconstruct the original data from any ten of the total 15 that you made. This is probably more robust than making a whole backup set since if you just duplicate all 10 discs and then have 5 failures, there's a high chance that you'll lose both a primary and its backup. Fancy RAID systems work something like this.

I think this should make sense and be interesting for high-school algebra students who use computers. Edit: I guess it is also pretty similar to Shamir secret sharing. Reed-Solomon is of course more widely used as an error-correcting code, with a slightly more involved explanation.

User none - MathOverflow

Answer by none for Unexpected applications of the fact that nth degree polynomimals are determined by n+1 points