National Semiconductor 48-bit and 56-bit ECC polynomials

[Eric Smith]

On Fri, Nov 18, 2016 at 7:40 AM, Paul Koning <paulkoning at comcast.net> wrote:

> I don't know enough math to do the work, but a little rubbed off from
> listening to those who do.
>
> CRC polynomials have special properties, they aren't arbitrary
> polynomials.  That reduces the number of possible choices dramatically.  In
> fact, I remember that finding a good one is hard work;
>

Finding only "good" polynomials and then testing those against the data is
far more work than doing the brute-force search of all order-n polynomials
that have a relatively small number of terms including x^0.  However,
National might not have restricted their search to a small number of terms,
which had been done in the early days to minimize hardware (number of XOR
gates, and resulting depth of XOR tree). By the mid-1980s that was less of
a concern. There is some evidence that using an order n polynomial with
roughly n/2 terms may typically be stronger than order n polynomials with
few terms, in which case a brute force search for a 56 bit polynomial
becomes almost completely intractable, short of a distributed search on a
large number of machines with GPUs.


> I would assume this means you can deduce the CRC polynomial by
> straightforward math from a few well chosen test data blocks.
>

If I had the hardware that wrote the disk in question, there are a lot of
things I could do, including that.

I may have to tell the owner of the disk drive that I can give him the
uncorrected data only.