3 ms·
> CRC style checksums are automatically a no-go. They're inherently sequential. AFAIK the linearity of CRCs allows them to be split, parallelized, and combined
by CodesInChaos 4y ago
> CRC style checksums are automatically a no-go. They're inherently sequential.
AFAIK the linearity of CRCs allows them to be split, parallelized, and combined. This is also the case for polynomial MACs, like GHash or Poly1305.
- AlotOfReading 4y agoYep, the only downside for CRC being that the recombination involves some expensive multiplications that are proportional to the total input length.
- CodesInChaos 4y agoFor Poly1305 you can use square-and-multiply to compute the exponentiation required for recombination, which has logarithmic cost, not linear. Are you sure a similar algorithm can't be applied to CRCs?
- AlotOfReading 4y agoSorry, I didn't phrase it well. It's also log(n) for CRCs via the same algorithm.