# A small algebraic signature you can exhaustively check

This educational calculation illustrates a linear fingerprint, not a storage
benchmark, security protocol, implementation of Pergamum, or measured error rate.

## Definition

Represent a block as four four-bit symbols [d0,d1,d2,d3]. Arithmetic is in
GF(16), represented with modulus x^4+x+1 (binary 10011). Addition is XOR.
Let p(x)=d0+d1*x+d2*x^2+d3*x^3 and S(d)=[p(1),p(2)].
Here 2 denotes the polynomial-basis field element x, not ordinary real arithmetic.
Input length, symbol order, modulus and evaluation points are fixed.

The first two coefficients map to [d0+d1, d0+2*d1]. The corresponding
two-by-two matrix is invertible because 1 and 2 are distinct. Consequently the
map has rank two: 16^4 inputs occupy 16^2 signatures evenly, 256 inputs each.
The program enumerates every input rather than sampling.

The difference [2,3,1,0] represents (x+1)(x+2); it evaluates to zero at both
points. XORing that difference into any input changes three symbols but retains
its signature. This does not contradict detection of all one- and two-symbol
changes in this fixed-length instance.

Each original has 255 distinct matching alternatives among 65,535 possible
different replacement blocks. Thus a uniform choice over *different* blocks
gives 255/65,535=1/257, whereas a uniform choice over all blocks gives 1/256.
Neither model describes an adversary choosing a matching alternative or
physical storage corruption. Signature width alone does not specify that risk.

## Reproduce

Downloads: [model](./model.mjs), [tests](./test.mjs), [enumerated results](./results.json).

Requires Node.js and no packages:

    node model.mjs
    node --test test.mjs

The tests compare all products with independent carryless multiplication and
polynomial long division, and all signatures with direct power-sum evaluation.
They check linearity for every input against every binary basis vector,
all input/collision partners, all one/two-symbol differences, and invalid input.
These are deterministic arithmetic checks, not independent research replication.

## Reading

Schwarz and Miller, ICDCS 2006, section 3.1 defines polynomial signatures;
section 4.2 distinguishes internal consistency from a collusion-resistant
protocol. The paper's additional randomization/blinding is outside this model.
https://www.ssrc.us/media/pubs/e368d255b625c27c9f49fe91ef025be645882ede.pdf

Hesela authored this small illustrative instance on 2026-10-23. No paper code,
datasets, figures or performance measurements are redistributed here.

## Length changes the two-symbol guarantee

The same eight-bit signature can have different detection guarantees when the
covered block grows. In the supplemental [calculation](./length-boundary.mjs),
[tests](./length-boundary.test.mjs) and [results](./length-boundary.json), the field,
modulus, coefficient order and evaluation points stay unchanged. Only the
number of input symbols changes. A symbol is four bits, not one byte.

| Input symbols | One-symbol differences | Undetected | Two-symbol differences | Undetected |
| --- | ---: | ---: | ---: | ---: |
| 4 | 60 | 0 | 1,350 | 0 |
| 14 | 210 | 0 | 20,475 | 0 |
| 15 | 225 | 0 | 23,625 | 0 |
| 16 | 240 | 0 | 27,000 | 15 |

There are N*15 one-symbol differences and N*(N-1)/2*15^2 two-symbol
differences: choose distinct positions and a nonzero XOR difference at each.
The four rows enumerate 73,185 differences, not all possible long input blocks.
Linearity makes a zero-signature difference invisible regardless of the
original block. These are exact counts within this defined set, not a device
error distribution.

The reason for the boundary is visible without trusting the program. The
nonzero element 2 has multiplicative order 15 in this representation, so
2^15=1. The signature contribution of position i is the column [1,2^i].
The columns at zero-based positions 0 and 15 coincide. Equal nonzero changes
at those positions therefore cancel at both evaluation points. There are
15 such pairs, one for each nonzero difference. For positions 0 through 14,
all columns are distinct; if the first component cancels, the two differences
must be equal, and their second components cannot cancel. This proves the
two-symbol result for this particular construction up to length 15.

This is Hesela's derivation for the teaching instance. Schwarz and Miller's
section 3.1 supplies the polynomial construction; the table is not a measurement
from that paper or Pergamum. It does not establish a bound for every finite-field
fingerprint.

### Keep the page identity with the checksum

The results include a 16-symbol block and a partner changed at positions 0
and 15. Their whole-block signatures match. Splitting both at a fixed boundary
into pages of 15 and 1 symbols, and retaining the ordered pair of page
signatures, exposes both changes. Simply XORing those page signatures back
into one value loses the distinction again.

That example assumes unchanged page boundaries, ordering, lengths and trusted
expected signatures. It is not authentication or proof of freshness. A checksum
contract must specify those inputs as well as its field and output width.

To reproduce the supplement:

    node length-boundary.mjs
    node --test length-boundary.test.mjs

The test oracle uses independent carryless multiplication with polynomial long
division and direct power sums. It checks all 73,185 tabulated differences,
every shorter length from 1 through 15, several nonzero originals and all
65,536 original four-symbol inputs. The original model, tests and results remain
unchanged.