🚀 go-pugleaf

In article <69133@cup.portal.com> lordSnooty@cup.portal.com (Andrew - Palfreyman) writes:
> On reading a couple of texts on error-correcting codes, the
> following question occurred to me:
> 
> What is an efficient method for deducing the checksum generating
> polynomial, given many examples of a block code with an appended checksum?

The simplest application of an error-checking polynomial (mapping other
cases, like preset to all 1's as in FDDI, to this is simple) is that
the valid messages are all multiples of some check polynomial c(x).
Given a number of message polynomials, m_i(x), their GCD will contain
c(x) as a factor, and if there are enough, there will probably be no
other factors.

It is not too difficult to extend this to handle a small number of
erroneous messages, by taking various subsets and applying sanity checks
to the GCD's to find the erroneous ones.

In summary, it's not a hard problem.  I can also deduce unknown (but
constant) preset strings by subtracting messages to cancel the constant
leading parts and applying this algorithm to the differences.  I can't
think of a difficult variation.  CRC's have *lots* of exploitable
mathematical structure to use in analysis.
-- 
	-Colin