Why are some mapping matrices obtained from primitive elements wrong?

[hhucchenyixiao]

Hello, I use your method to try to find mapping matrices in $GF(2^4)$ and $GF((2^2)^2)$ $GF(2^4): x^4+x+1$, with primitive elment $α(x)$ $GF((2^2)^2) : x^2 + x + (10)$ , with primitive element: $β(x) = (01)x + (00)$ $GF(2^2) : x^2 + x + 1$, with primitive element: $x + 0$

There are 8 primitive element in the $GF(2^4)$, which is $x, x+1, x^2, x^2+1, x^3+1, x^3+x+1, x^3+x^2+1, x^3+x^2+x$ Then I try to map these eight primitive elements to $β(x)$, and build eight mapping matrices But the results of the last four primitive elements are wrong

For example, take the last primitive element $α(x) =x^3+x^2+x$ then $α(x)^3 = 0x8, α(x)^7 = 0x4, α(x)^{11} = 0x2, α(x)^0 = 0x1 $ so I get the mapping matrices $M = [β(x)^3\ β(x)^7\ β(x)^{11}\ β(x)^0] = [0xe\ 0xb\ 0xc\ 0x1]$ $M^{-1} = [0xf\ 0xd\ 0xa\ 0x1$]

For $p(x) = x^3+x^2+x+1$ and $q(x) = x^3$ satisfy $p(x)q(x)=1$ in $GF (2^4)$ $Map(p(x))=m(x)=(10)x+(00)$ in $GF((2^2)^2)$ $Map(q(x))=n(x)=(11)x+(10)$ in $GF((2^2)^2)$ $m(x)*n(x) = (10)x+(10) $

It's obviously wrong, Becasue $m(x)n(x)=Map(p(x)q(x))=Map(1)=(00)x+(01)$

but I really can't find the reason for it. Can you help me? any help will be greatly appreciated!

When mapping GF(24) to GF((22)2), only 4 of the 8 primitive elements can be used for mapping, so your result is correct.

Note - the values you have for powers of α(x)=x3+x2+1 are for GF(24)=x4+x3+1. For GF(24)=x4+x+1, the powers of α(x)=x3+x2+1 in hex are: α(x)6=8 α(x)e=4 α(x)7=2 α(x)0=1 However, this doesn't matter, since α(x)=x3+x2+1 is one of the four primitive elements that won't work.

This becomes an issue for larger fields. To map GF(28) to GF(((22)2)2), only 8 of the 128 primitive elements will work. To map GF(216) to GF((((22)2)2)2), only 16 of the 32768 primitive elements will work.

[jeffareid]

When mapping $GF(2^4)$ to $GF((2^2)^2)$, only 4 of the 8 primitive elements can be used for mapping, so your result is correct.

This becomes an issue for larger fields. To map $GF(2^8)$ to $GF(((2^2)^2)^2)$, only 8 of the 128 primitive elements will work. To map $GF(2^{16})$ to $GF((((2^2)^2)^2)^2)$, only 16 of the 32768 primitive elements will work.

[hhucchenyixiao]

Sorry, I mistakenly took $α(x) =x^3+x^2+1$ as $α(x) =x^3+x^2+x$ above, I have corrected the typo.

And thank you for your affirmation, but why can't these four work?

$\forall \alpha$ is primitive elements, \ $\forall u,v \in GF(2^4)$ can be expressed as the power of $\alpha$\ We assume that $u=\alpha^i, v=\alpha^j$

we let $Map(\alpha^n)=\beta^n,\ n \in \mathbb{Z} _{16}$\ $Map(uv)=Map(\alpha^i\alpha^j)=Map(a^{i+j})=\beta^{i+j}= \beta^i \beta^j=Map(\alpha^i)Map(\alpha^j)=Map(u)Map(v)$

The condition of isomorphic mapping is satisfied, So why can't some primitive elements be used as mappings

[hhucchenyixiao]

I seem to have found the reason. Not all the primitive elements can meet $Map(a+b)=Map(a)+Map(b)$.

$\beta^2+\beta+(10)=0$ If $Map(\alpha^n)=\beta^n,\ n \in \mathbb{Z} _{16}$\ Then $\alpha^2+\alpha+Map^{-1}(10)=Map^{-1}(\beta^2+\beta+(10))=Map^{-1}(0)=0$

But $α(x) =x^3+x^2+x$, $Map^{-1}(10)=M^{-1} (0010)^T=0xa$ Then $\alpha^2+\alpha+Map^{-1}(10) = (0xe)^2+0xe+0xa = 0xf$

So we can't set $\alpha(x) = x^3+x^2+x$

I am very grateful for your example, which gives me a deeper understanding of the composite field!

[jeffareid]

You had it correct before, the issue was addition: $map(a)+map(b) = map(a+b)$, which fails for 4 of the primitive elements. Map(0) can never fail, map(0) will always = 0, since the values in the mapping matrix are not used.

[hhucchenyixiao]

You had it correct before, the issue was addition: map(a)+map(b)=map(a+b), which fails for 4 of the primitive elements. Map(0) can never fail, map(0) will always = 0, since the values in the mapping matrix are not used.

You're right. I changed it back。 But is

$$ \alpha^2+\alpha+Map^{-1}(10)=0 \iff additive\ \ homomorphism $$

$$ \beta^4+\beta+1=0 \iff additive \ homomorphism $$

correct ?

The necessity is obvious, but I can't prove the sufficiency.

[jeffareid]

Isomorphic mapping requires $map(a) + map(b) = map(a+b)$ and $map(a) \ map(b) = map(a \ b)$ . I'm not sure how to prove this is sufficient, other than a brute force check for all elements of $GF(2^4)$ mapped to elements of $GF((2^2)^2)$, which is 16 x 16 = 256 combinations of $a$ and $b$.

Using your multiplication example (f and 8), with $α(x) = x = 2$ and $β(x) = x = 4$:

For $GF(2^4)$: $α(x)^c + α(x)^3 = f + 8 = 7 = α(x)^a$ For $GF((2^2)^2)$: $β(x)^c + β(x)^3 = d + e = 3 = β(x)^a$ $map(f) + map(8) = map(7)$ $d + e = 3$

This will fail for $α(x) = x^3+x^2+x = e$

I don't understand your additive homomorphism examples, that should be:

For $GF(2^4)$: $α(x)^4 +α(x) + 1 = 0 = α(x)^4 +α(x) + α(x)^0$ For $GF((2^2)^2)$: $β(x)^2 + β(x) + 2 = 0 = β(x)^2 + β(x) + β(x)^5$

However what is needed is to map from $GF(2^4)$ to $GF((2^2)^2)$ to show $map(a)+map(b)+map(c) = map(a+b+c)$: $β(x)^4 +β(x) + β(x)^0 = 5 + 4 + 1 = 0$. This will only work for 4 of the 8 primitive elements of $GF(2^4)$.

[hhucchenyixiao]

If $α(x) =x^3+x^2+x$\ $α(x)^3 = 0x8, α(x)^7 = 0x4, α(x)^{11} = 0x2, α(x)^0 = 0x1$\ Then our mapping matrix only guarantees \ $Map(α(x)^3)=\beta^3, Map(α(x)^7)=\beta^7, Map(α(x)^{11})=\beta^{11}, Map(α(x)^0)=\beta^0$\ But $Map(\alpha(x)^n)=\beta^n,n={1,2,4,5,6,8,9,10,12,13,14}$ is not necessarily correct\ So the isomorphism of multiplication may not hold.

[hhucchenyixiao]

I changed my mind again😂. I think the isomorphism of addition is always true.\ $\forall u,v \in GF(2^4)$ their corresponding coefficient matrices are $U,V$\ And we use this method to get any mapping matrix: $M$, $M(U+V) = MU+MV$, This shows that $Map(u+v)=Map(u)+Map(v)$

[jeffareid]

Since $map(α(x)^i) = β^i$, then $map(α(x)^i) \ map(α(x)^j) = map(α(x)^i \ α(x)^j)$ will work for all 8 primitive elements, but $map(α(x)^i) + map(α(x)^j) = map(α(x)^i+α(x)^j)$ will fail for 4 of the 8 primitive elements $α(x)$ .

Using the example $f+8 = 7$, with $α(x) = x^3 + x^2 + x$, that becomes: $α(x)^c + α(x)^3 = α(x)^5$, but $β(x)^c + β(x)^3 \ne β(x)^5$ : $d+e \ne 2$

[hhucchenyixiao]

The method only guarantees that the mapping under the four exponents must be true.

For example, $α(x) =x^3+x^2+x$ the method only guarantees $Map(\alpha(x)^m)=\beta^m, m=3,7,11,0$\ $M = [β(x)^3\ β(x)^7\ β(x)^{11}\ β(x)^0] = [0xe\ 0xb\ 0xc\ 0x1]$

But if m = 12, $α(x)^{12} = 0xf$\ Because $M[1111]^T=[1000]^T$\ So $Map(α(x)^{12}) = Map(0xf)=0x8=\beta^6 \ne (\beta^{12}=0xd)$

[jeffareid]

To clarify what you've commented in hex: $α(x)^3 + α(x)^7 + α(x)^b + α(x)^0 = α(x)^c = f$ but $β(x)^3 + β(x)^7 + β(x)^b + β(x)^0 = β(x)^6 = 8 \ne β(x)^c$

This is just another example of $map(a)+map(b) = map(a + b)$ failing for 4 of the 8 primitive elements.

To avoid potential confusion, the example is $GF(2^4): x^4 + x+ 1$, which has 4 roots {$2,3,4,5$}, $(x-2)(x-3)(x-4)(x-5) = x^4 + x + 1$, and these 4 roots also happen to work for mapping to $GF((2^2)^2)$. However for $GF(2^8):x^8 + x^4 + x^3 + x^2 + 1$, none of the 8 roots {$02,04,10,1d,4c,5f,85,9d$} can be used to map to $GF(((2^2)^2)^2): x^2 + x + c$. Instead a different set of 8 primitive elements {$12,13,18,19,5c,5d,80,81$} can be used for mapping. The point here is that the roots of the primitive polynomial do not always correspond to the primitive elements that can be used to map to a composite field.

[hhucchenyixiao]

We cannot assume that $Map(\alpha^c)=\beta^c$\ By mapping matrix $M$, we can get $Map(\alpha^c)=\beta^6$\ So \ $Map(\alpha^3+\alpha^7+\alpha^b+\alpha^0)=Map(\alpha^c)=\beta^6$\ $Map(\alpha^3)+Map(\alpha^7)+Map(\alpha^b)+Map(\alpha^0)=\beta^3+\beta^7+\beta^b+\beta^0=\beta^6$

Obviously, the homomorphism of addition still holds

[jeffareid]

Every finite field with the same number of elements is isomorphic in addition and multiplication: $map(α(x)^i) + map(α(x)^j) = map(α(x)^i+α(x)^j)$ $map(α(x)^i) \ map(α(x)^j) = map(α(x)^i \ α(x)^j)$

Any such mapping can always be implemented via a matrix multiply which will require $map(α(x)^k) = β(x)^k$ for any $k$.

Isomorphism requires finding a way to map between fields. For the method I used, this requires finding the right choice of primitive element for $α(x)$. Unfortunately, I'm not aware of a method to find primitive elements that will work for isomorphic mapping other than trial and error.

[hhucchenyixiao]

if $α(x) =x^3+x^2+x$, then $x^3=\alpha^3, x^2=\alpha^7, x^1=\alpha^b, x^0=\alpha^0$\ bulit mapping matrix $M = [\beta^3\quad \beta^7\quad \beta^b\quad \beta^0]$ $\iff$ built a map $\Phi$, $\Phi(k_3\alpha^3+k_2\alpha^7+k_1\alpha^b+k_0)=k_3\beta^3+k_2\beta^7+k_1\beta^b+k_0\quad k \in \mathbb{Z}_2$

$\forall u,v \in GF(2^4)$ we can express as \ $u = a_3x^3+a_2x^2+a_1x+a_0=a_3 \alpha^3+a_2\alpha^7+a_1\alpha^b+a_0\alpha^0$\ $v = b_3x^3+b_2x^2+b_1x+b_0x=b_3\alpha^3+b_2\alpha^7+b_1\alpha^b+b_0\alpha^0$\ $uv= (a_3x^3+a_2x^2+a_1x+a_0)(b_3x^3+b_2x^2+b_1x+b_0)\ mod\ (x^4+x+1)=c_3x^3+c_2x^2+c_1x+c_0=c_3\alpha^3+c_2\alpha^7+c_1\alpha^b+c_0\alpha^0$

$\Phi(u)=\Phi(a_3x^3+a_2x^2+a_1x+a_0)=a_3\beta^3+a_2\beta^7+a_1\beta^b+a_0=a_3(\beta^b)^3+a_2(\beta^b)^2+a_1\beta^b+a_0$\ $\Phi(v)=b_3(\beta^b)^3+b_2(\beta^b)^2+b_1\beta^b+b_0$\ $\Phi(uv)=c_3(\beta^b)^3+c_2(\beta^b)^2+c_1\beta^b+c_0$

We write $\beta^b$ as $y$

$\Phi(u)=a_3(y)^3+a_2(y)^2+a_1y+a_0$\ $\Phi(v)=b_3(y)^3+b_2(y)^2+b_1y+b_0$\ $\Phi(uv)=c_3(y)^3+c_2(y)^2+c_1y+c_0$

If the isomorphism of multiplication is to be established, we need $\Phi(u)\Phi(v)=\Phi(uv) \iff y^4+y+1=0 \iff (\beta^b)^4+\beta^b+1=0$\ But $(\beta^b)^4+\beta^b+1=0xa \ne 0$, So the isomorphism of multiplication is failed.

[jeffareid]

For $α(x)=x^3+x^2+x$, isomorphism of multiplication will pass, but isomorphism of addition will fail.

As another example from an earlier comment:

For $GF(2^4):x^4+x+1$, the 4 roots of $x^4+x+1$ are {2 3 4 5}, and can be used to map from $GF(2^4):x^4+x+1$ to $GF((2,2)^2):x^2 + x + 2$, but this not a general rule, and in other cases, it doesn't work.

For $GF(2^4):x^4+x^3+1$, the 4 roots of $x^4+x^3+1$ are {2 4 9 e}, none of which can be used to map from $GF(2^4):x^4+x^3+1$ to $GF((2,2)^2):x^2 + x + 2$. The primitive elements that can be used to map are {6 7 c d}.

[hhucchenyixiao]

I agree that the roots of primitive polynomials may not be used to isomorphic map. But in my view

$$ GF(2^4) = \frac{GF(2)[x]}{r(x) = x^4 + x + 1} $$

We can first determine any primitive element in $GF(2^4)$, which is $\alpha$, then calculated $n,\quad \alpha^n=0x2$. \ So $r(\alpha^n)=(\alpha^n)^4 + (\alpha^n)+ 1 = 0$ If the primitive element $\beta$ in the $GF(2^2)^2$ can meet $r(\beta^n)=(\beta^n)^4 + (\beta^n)+ 1 = 0$, This pair $\alpha\quad \beta$ can be used to map from $GF(2^4)$ to $GF((2^2)^2)$

[jeffareid]

In the case of $r(x) = x^4 + x^3 + 1$, for the 4 primitive elements $α$ = {6 7 c d} that can be used to map from $GF(2^4)$ to $GF((2^2)^2)$ $α^4 + α^3 + 1 \ne 0$ , and similarly, $β^4 + β^3 + 1 \ne 0$. A method is needed that is independent of the choice for $r(x)$.

$β=4$ is a predetermined choice for efficiency purposes. The polynomials are also predetermined, leaving $α$ as the only variable to be determined based on being able to map from $GF(2^4)$ to $GF((2^2)^2)$ , and there may be an optimal choice of $α$, at least for a hardware implementation.

To determine if $α$ is a primitive element for $GF(2^n)$, let $p$ = all combinations of factors of $2^n-1$. For $n=4$, $p$ = {3 5}, and only two tests are needed, $α^3 \ne 1$ and $α^5 \ne 1$. For $GF(2^8)$, $p$ = {15 51 85}.

There are alternative methods, such as the case when $r(x)$ is primitive. Choose $α = 2$ and $β = 4$. Let $r'(x) = r(x)$, except that $r'(x)$ has coefficients in $GF((2^2)$, then $r'(x)$ has two primitive factors. For example, $r'(x) = x^4 + x^3 + 1 = (x^2 + 2x + 2) \ (x^2 + 3x + 3)$ Either of these factors can be used as the polynomial for $GF((2^2)^2)$, but due to the $2x$ or $3x$ term, they are not as efficient as choosing $x^2 + x + 2$, and searching for a primitive element $α$ that can be used for mapping.