There are several ways to do this. We know that the polynomial has to be of degree n, so that it is in the form f(x) = ax^n + bx^(n-1) + cx^(n-2) ... + z. We could set up a system of n equations by treating the coefficients as variables and then solving them.
That's a good way to do it. In many ways it's better than what I came up with. Since I was writing the code to do this myself, I didn't want to bother writing a matrix math implementation. I also didn't want to use a general purpose matrix math library since I planned on making my own standalone library to do forward error correction.
Anyway, what I decided to do was simply construct the polynomial using a pretty basic algorithm. Imagine a polynomial of n terms where all but one term is zero for each input value that we're interested in.
So for instance, let's say we want F(0) = a, F(1) = b, F(2) = c. First we'll construct a function f(x) such that f(0) = a, f(1) = 0, and f(2) = 0. Well we see it has two roots so it's in the form f(x) = (x-1)(x-2)[something]. To figure out the [something] part we just evaluate the f(0) we have so far, and we get f(0) = 2. But we want f(0) to be a, so we multiply f(x) by a/2. Thus our final f(x) = a/2 * (x-1)(x-2). Now let's calculate g(x) such that g(0) = 0, g(1) = b, and g(2) = 0. So we know g(x) = x(x-2)[something]. So far g(1) = -1, but we need it to be b, so we multiply by -b. Thus g(x) = -b * x(x-2).
Once we have all of these sub-functions, we simply add them all together and get F(x). Each term will be zero for every input value except one. For that one value, the term will produce the desired output value. We can multiply everything out and collect terms and then we'll have our standard polynomial in the form F(x) = ax^n + ....
This is a complex-sounding idea, perhaps, but it turned out to be fairly easy to code. All I needed was a polynomial class with a few functions:
1. Multiply by x
2. Multiply by a constant
3. Add together
4. Evaluate
There's one big problem with this approach: it's SLOW. The naive algorithms I used are O(n^3). For a file of n bytes, we need to construct n terms. Each term requires n polynomial multiplications and additions. Each polynomial multiplication and addition required n real multiplications and additions. Awful! I ran it on a 1KB file and it took about 5 minutes.
There's also another issue we have to address before continuing. All of this is going on in what's called a finite field, which might require some explanation.
First of all, I'm only working with integers in this program. All of the file data is just bytes, and bytes are just integers. There are two problems with this. One is that computers can only represent finite integers. You can get overflow errors if you multiply two large integers. Even though all of the data values in our file are small, there's no guarantee that the coefficients we generate are small. There's also no guarantee that the redundant data we generate using the polynomial is small. In fact, if we're talking about a polynomial of degree 1,000,000 (which you'd need to encode a 1 megabyte file!), I can guarantee that the integers it generates for the redundant data are going to be REALLY HUGE. What is 1,000,001^1,000,000? Well that's just the first term for the first redundant piece of data. If you go to the GMP homepage you can plug that in and it says:
The result of executing 1000001^1000000 is:
computation took 1138 ms
result is about 6000000 digits, not printing it
Now imagine you're adding redundancy to a DVD image requiring a polynomial of degree 4 billion. We're talking seriously large integers.
The other problem is with the construction of F(x) above. During the construction of the first term, f(x), we had to multiply by a/2. What if a is odd? Now our coefficients aren't even integers!
Finite fields save us from both problems. In a finite field, addition and multiplication always produce another member of the field. And all field members (except 0) have a multiplicative inverse. Very useful!
Let's look at an easy example of a field. Pick a prime number, then take the integers modulo that number. That's a finite field. Let's look at p = 5. The members of the field are {0, 1, 2, 3, 4}. What happens if you do 3+4? 3 + 4 = 7, 7 = 2 modulo 5, so the result is 2. How about if you multiply 2 and 4? 2 * 4 = 8, 8 = 3 modulo 5, so the result is 3. That's how the field solves the problem of overflows. How about that inverse problem? What is the inverse of 2 in our example? Well the inverse of 2 is a number x such that 2*x = 1, right? In real numbers, x = 1/2. In our field, x = 3! Because 2 * 3 = 6, and 6 = 1 modulo 5. How about the inverse of 4? 4 is an odd one because it turns out 4 is its own inverse. 4 * 4 = 16, and 16 = 1 modulo 5.
Anyway, that is a very nice solution to our two problems. As long as we do all of our arithmetic in a finite field, we'll be safe. So what field do we choose?
For my initial testing, I chose a simple field like in the example, but with p = 257. That's the smallest prime that holds all byte values.
Note that there is still a slight problem here. The largest value that a byte can hold is 255. The largest value in our field is 256. What happens if our polynomial produces a 256 as one of the redundancies? We couldn't encode it in a single byte so we'd have to use some sort of UTF-8-like encoding for integers! That adds a slight bit of overhead to our redundancy, which is not desirable.
So now we have two more problems:
1. This process is REALLY SLOW because of the O(n^3) algorithm
2. The redundancy information has overhead that we don't want
