Appendix E — the key equation $S(z)\sigma(z) \equiv \omega(z) \bmod z^\delta$

Let $K$ be a finite field of characteristic $2$, let $M \subseteq K^*$ be the support of a binary word $p$, and let $\delta \ge 0$. With the error locator $\sigma(z) = \prod_{x \in M} (1 - xz)$, the error evaluator $\omega(z) = \sigma(z) \sum_{x \in M} \frac{xz}{1 - xz}$, and the syndrome polynomial $S(z) = \sum_{\ell = 1}^{\delta - 1} p(\alpha^\ell) z^\ell$ where $p(\alpha^\ell) = \sum_{x \in M} x^\ell$,

This congruence is the key equation of Berlekamp's BCH decoding algorithm as adapted in Appendix E: the syndrome, which is public, is tied by it to the unknown error locator, whose roots are the inverses of the elements of $M$.

Formalization Note. $\omega$ is written without division, as $\sum_{x \in M} xz \prod_{y \in M \setminus \{x\}} (1 - yz)$. The congruence modulo $z^\delta$ is stated as divisibility of $S\sigma - \omega$ by $X^\delta$. The paper's text says "we are given $p(\alpha^\ell)$ for $\ell = 1, \dots, \delta$", but $S$ uses only $\ell \le \delta - 1$; we follow the definition of $S$. The binary case of the paper's $q$-ary words is stated. The statement holds for every $\delta$ (at $\delta = 0$ it is trivial), so no lower bound on $\delta$ is imposed.