1. A method for decoding an Error Correction Code (ECC), comprising: using hardware-implemented logic, producing from a set of bits, which represent data that has been encoded with the ECC, multiple syndromes by applying to the bits vector operations in a vector space, wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space; generating, based on the multiple syndromes, an Error Locator Polynomial (ELP) whose roots are indicative of locations of respective errors in the set of bits; and identifying at least some of the roots of the ELP and correcting the errors indicated by the identified roots.