Counting equivalent funtions over GF(2^n)

113 Views Asked by At

Let $F = GF(2^n)$ specified using a particular irreducible polynomial of degree $n$. Now, let $f(x) = x^{-1}$ in $F$, except we define $f(0):=0$. Let $G$ and $H$ be invertible $n \times n$ matrices over $GF(2)$, i.e. $G,H \in GL_n(GF(2))$ and let $h(x) = Hx$ and $g(x) = Gx$ where multiplication is operating on $x$ as a length $n$ vector over $GF(2)$.

I am interested in counting, when allowing all possible combinations of (invertible) matrices $G$ and $H$, the number of pairs $(g,h)$ such that $g \circ f \circ h = f$.

1

There are 1 best solutions below

1
On

in that case:

I dont have a full answer but some progress is made:

as it is said $G$ is invertible so we have $G^{-1} f(X) = f(H X)$.

now since $f$ is considering the vector of $H X$ as an element of $GF(2^n)$, it is convenient to express $H = [\beta_1 \beta_2 ... \beta_n]$ and $G^{-1} = [\gamma_1 \gamma_2 ... \gamma_n]$ in which $\beta_i$ and $\gamma_j$ are the elements of field which their vector representations are in columns of $H$ and $G^{-1}$.

now examining the equation we get for nonzero $X$ we have: $(\sum \gamma_i x^{-1}_i) \times (\sum \beta_j x_j) = 1$

so, $\sum \beta_i \gamma_j x^{-1}_i x_j = 1$

on the other hand $X X^{-1} = 1$, so we have, $\sum x_i \alpha^i \sum x^{-1}_j \alpha^j = 1$ ($\alpha$ is the primitive element), so we have, $\sum \alpha^{i+j} x_i x^{-1}_j = 1$ is the only equation satisfied.

so the $\beta_i \gamma_j = \alpha^{i+j}$ works, which is $g(x) = a x$ and $h(x)=a^{-1} x$.