Implementing the Mceliece Encryption - making the Generator Matrix I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding theory to understand it.

In brief given MCE parameters $n, k, t$, such that it is over $GF(2^m)$, $n = 2^m$, $k = n - mt$ is the dimension of the linear code and $t$ is the no. of errors the code will correct, the public key is $X = S.G.P$, where $S$ is a $k$ x $k$ non-singular matrix, $G$ is the $k$ x $n$ generator matrix for the linear code and $P$ is a $n$ x $n$ permutation matrix. 

Figuring out how to get $G$ is the reason for the question. I'd like to better understand how the generator matrix is built such that its elements are only $0$ or $1$, once we have the irreducible polynomial of degree $t$, support $L$ and parity check matrix $H$. $L$ &amp; $H$ are composed of the elements of $GF(2^m)$ represented as polynomials in binary form, e.g. $x^4 + x^2 + 1$ is represented as $10101$.

I understand there are many methods of getting to the generator matrix but found limited information online. I'd welcome a simplified explanation of the maths/algorithm or any pointers to sites/books which would help out on this.
I'm going to assume you are using binary Goppa codes. That means, that you take a support $\mathbf{L} \in \mathbb{F}_{2^m}$, a Goppa polynomial $\Gamma$ of degree t with coefficients in $\mathbb{F}_{2^m}$ and build all codewords of a GRS code, and then intersect these with $\mathbb{F}_2^n$, resulting in a code that is actually a subset of $\mathbb{F}_2^n$ (and not of $\mathbb{F}_{2^m}^n$). This is the classical definition used by McEliece in his original proposition.

As you might have already read, the binary Goppa code has a check matrix (there is an error in the Wikipedia article, this one is correct):
$$H_{grs} = \begin{pmatrix} 1 &amp; \dots &amp; 1 \\
L_0 &amp; \dots &amp; L_{n-1}\\
L_0^2 &amp; \dots &amp; L_{n-1}^2\\
\vdots &amp; &amp; \vdots\\
L_0^{t-1} &amp; \dots &amp; L_{n-1}^{t-1}\end{pmatrix}
\begin{pmatrix}
\frac{1}{\Gamma(L_0)} &amp; &amp; \\
&amp; \ddots &amp; \\
&amp; &amp; \frac{1}{\Gamma(L_{n-1})}
\end{pmatrix}$$

Now, are you are well aware, this is a $t \times n$ matrix in $\mathbb{F}_{2^m}$ and will thus give you codewords in $\mathbb{F}_{2^m}^n$. But we are interesed in code words only in $\mathbb{F}_{2}^n$. One can get a check matrix that gives only codewords in $\mathbb{F}_2$ by expanding every entry in the matrix in a basis of $\mathbb{F}_{2^m}$.

This means, if your entry of the matrix is represented as as vector $0101$ in $\mathbb{F}_2^4$ (for $m=4$), you would expand this entry as four entries and write them in four rows: 0, 1, 0, 1.

Example:
Let one of your rows of your check matrix $H_{grs}$ be
$$\begin{pmatrix}0101&amp; 1010 &amp;0001&amp; 1000\end{pmatrix}$$
then you would write this as
$$\begin{pmatrix}
0 &amp; 1 &amp; 0 &amp; 1\\
1 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 1 &amp; 0 &amp; 0\\
1 &amp; 0 &amp; 1 &amp; 0\end{pmatrix}$$
You do this for all your rows and you will end up with a check matrix $H$ of size $mt \times n$, since you are expanding every row by $m$ rows. From now on, you only work over $\mathbb{F}_2$; using this check matrix, you'll get code words in $\mathbb{F}_2^n$. Note: You will have to do Gauss elimination at this point to get rid of rows that give the same equation. This will reduce your row number and give you a reduced check matrix of size $(n-k) \times n$, where k is the dimension of your binary code.

Now, to get a generator matrix $G$ for that code, you look for a full-rank matrix with $H^\top G=0$. There are many ways to achieve this, and you should find enough material on this. For example: http://en.wikipedia.org/wiki/Parity-check_matrix. Keep in mind, that if $H$ is a check matrix for $G$, then $G$ is a check matrix for $H$. So you build $G$ by pretending $H$ is a generator and you want to find a check matrix for that code.

I hope this is what you asked for.