1. A method for decoding an Error Correction Code (ECC), the method comprising: accepting coefficients, including at least first and second coefficients, of an Error Locator Polynomial (ELP) that is defined over a vector space and has at least one root that is indicative of a location of an error in a set of bits, which represent data that has been encoded with the ECC; representing the first coefficient using a first basis of the vector space, and representing the second coefficient using a second basis of the vector space, different from the first basis; using processing circuitry, identifying the root of the ELP by applying algebraic operations to the coefficients, such that the algebraic operations are applied to the first coefficient using the first basis, and to the second coefficient using the second basis; and correcting the error responsively to the identified root of the ELP.