Now, let's erase m values at locations E={Ej}, j=0..m-1. For each Ej, we can construct polynomial Pj(Z) of degree m-1 that evaluates to 1 at Ej and to 0 at all other locations in E. From Sum Xi Pj(Zi) = 0 we get Xj=Sum[i!=j] Xi Pj(Zi) (note that the sum is actually over all known Xi). {Pj(Zi)} is in fact the decoding matrix. Computing it is O(nm)=O(km^2) (not O(km) as I put above).
I have that algorithm implemented in my ErrorZ project on GitHub: https://github.com/OlegMazurov/ErrorZ/blob/master/src/main/j... More advanced stuff, like decoding up to m-1 errors, can also be found there.
Using a general matrix inversion is indeed inefficient, and becomes impractical for large k. However, the special-purpose row reduction algorithm I mentioned gets to O(nm^2) which is much better, although worse than the O(nm) algorithm you mentioned, which makes sense given that that one handles more specific RS codes.
Thanks for elaborating! It's reminding me that I really should brush up on coding theory, though -- do you have any resources/textbooks you'd recommend for someone familiar with the mathematical background? (Finite fields, etc.)
If I ever do use it or write about it, I'll make sure to cite you. Thanks again!