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; 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; wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space; wherein each basis is selected such that vector operations used for producing the respective syndrome comprise a multiplication of a sparse matrix; wherein the syndromes are defined over a field having a primitive element, and wherein selecting each basis comprises defining a set of basis elements as respective multiples of a given vector by different powers of the primitive element of the field.