User none - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T09:22:42Z http://mathoverflow.net/feeds/user/20416 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85065/unexpected-applications-of-the-fact-that-nth-degree-polynomimals-are-determined-b/85110#85110 Answer by none for Unexpected applications of the fact that nth degree polynomimals are determined by n+1 points none 2012-01-07T05:17:13Z 2012-01-07T05:33:28Z <p>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.</p> <p>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.</p>