Proper way to create Goppa code check matrix?

I'm trying to figure out what is the correct way to compute a check matrix for a binary Goppa code. So far (searching through the publications) I've found more than one possibility to do that, and I'm not sure how all those are related.

Suppose I have a Goppa code with irreducible Goppa polynomial $g(x)$ of degree $t$ over $GF(2^m) \simeq F[x]/F[p(x)]$ where $p(x)$ is defining polynomial of the field with degree $m$, and a support $\{l_1, l_2, l_3, \dots\} \subseteq GF(2^m) = \{u^0, u^1, u^2, \dots, u^{2^m-1}\}$.

In various sources, following three ways are described to create a check matrix.

  • Marta Giorgetti, Interesting examples on maximal irreducible goppa codes, page 2:

$ H_1 = \left( \begin{array}{cccc} \frac{1}{g(l_1)} & \frac{1}{g(l_2)} & \dots & \frac{1}{g(l_n)} \\ \frac{l_1}{g(l_1)} & \frac{l_2}{g(l_2)} & \dots & \frac{l_n}{g(l_n)} \\ \vdots & & & \\ \frac{l_1^{t-1}}{g(l_1)} & \frac{l_2^{t-1}}{g(l_2)} & \dots & \frac{l_n^{t-1}}{g(l_n)} \\ \end{array} \right) $

  • In the same paper, page 3:

$ H_2 = \left( \frac{1}{x - l_1}, \frac{1}{x - l_2}, \dots, \frac{1}{x - l_3} \right) $ (resulting polynomials are expanded as vertical vectors)

  • In Engelbert, Overbeck, Schmidt, A summary of McEliece-type cryptosystems and their security, page 10:

$H_3 = XYZ$

where

$ X = \left( \begin{array}{cccc} g_t & 0 & \dots & 0 \\ g_{t-1} & g_t & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ g_1 & g_2 & \dots & g_t \\ \end{array}\right) $

$ Y = \left( \begin{array}{cccc} 1 & 1 & \dots & 1 \\ l_1 & l_2 & \dots & l_n \\ l_1^2 & l_2^2 & \dots & l_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ l_1^{t-1} & l_2^{t-1} & \dots & l_n^{t-1} \\ \end{array}\right) $

$ Z = \left( \begin{array}{cccc} \frac{1}{g(l_1)} & & & \\ & \frac{1}{g(l_2)} & & \\ & & \ddots & \\ & & & \frac{1}{g(l_n)} \\ \end{array}\right) $

My question is why there are more different definitions - whether they are equivalent, or serve a different purpose, and which of those (and why) would work with the algebraic decoding algorithm described in the Overview paper.

Thanks

-exa

EDIT - additional question:

All three matrices probably have something in common (e.g. $YZ = H_1$). Question is: What impact does the additional information in H (e.g. the $X$ matrix) have on code properties, and how would that affect/enhance the decoding?

0
2022-07-25 20:40:56
Source Share
Answers: 0