libecc: Elliptic Curve Cryptography C++ Library

Main Page Reference Manual Compound List File List

Today, 24 November 2004, I found the answer to the question why #E₀ + #E₁ = 2(q + 1). It is actually quite trivial. The reason is simply this:

The number of points on a given elliptic curve is equal to

#E = 2 + 2 $\kappa$

where $\kappa$ is the number of different non-zero x coordinates for which there is a solution (and thus exactly two solutions) to the elliptic curve equation E: x³ + ax² + b = y² + xy.

The first 2 takes the point at infinity and the point with x is zero (0, $\sqrt{b}$ ) into account.

After dividing the elliptic curve equation by x², we see that there will be a solution for a non-zero value of x when x + a + b/x² = (y/x)² + y/x. And because of theorem 5, this only has a solution when Tr(x + a + b/x²) = 0.

In other words, when the trace of a is changed from 0 into 1, then there will be solutions for exactly the other non-zero values of x!

Therefore, with #E₀ = 2 + 2 $\kappa_0$ and #E₁ = 2 + 2 $\kappa_1$ as defined in the chapter "Cracking parameter a of the elliptic curve", we can conclude that $\kappa_0$ + $\kappa_1$ equals the total number of possible non-zero values of the field: q - 1. And thus #E₀ + #E₁ = 4 + 2(q - 1) = 2(q + 1).

The following might be a very important result, since I never saw it anywhere in literature yet (please contact me if you know whether or not this is indeed new):

The order of an elliptic curve over $\mathbb{F}_{2^m}$ is equal to (assuming Tr(a) = 0, otherwise it is 2(q + 1) minus this) 2 plus 2 times the number of values of x for which Tr(x) = Tr(b/x²). Note that due to Frobenius $Tr(b/x^2) = Tr(\sqrt{b}/x)$ .

If its new, then I hereby claim it ;).

It has been two years since I wrote something, but lets go again.

In order to find some relationship between b and #E we'll start with calculating #E₀ for different values of m, setting a=0 and b=1. The choice for a is irrelevant as has been shown before. The choice for b=1 is made because it is the only value that will be independent of the field (using b=0 gives a singular curve) so that comparing them with different values of m makes sense.

Thus, given the curve E: y² + xy = x³ + 1 over $\mathbb{F}_{2^m}$ , #E was calculated by running over all non-zero values of x and then counting how many times Tr(x) = Tr(1/x). Multiplying this value with 2 and adding 2 then gives #E as shown above. The program used to do these calculations can be found in testsuite/point/pointcount.cc.

The results are as follows.

Table 1.
m	#E
2	8
3	4
4	16
5	44
6	56
7	116
8	288
9	508
10	968
11	2116
12	4144
13	8012
14	16472
15	33044
16	65088
17	130972
18	263144
19	523492
20	1047376
21	2099948
22	4193912
23	8383412
24	16783200
25	33558844
26	67092488
27	134225284
28	268460656
29	536830604
30	1073731736
31	2147574356

I looked long and hard at those numbers and believe it or not, I came up with a structure.

First of all, you have to realize that each of those numbers where calculated as $2 + 2 \cdot count$ , so we might as well go back to that number.

Table 2.
m	(#E - 2)/2
2	3
3	1
4	7
5	21
6	27
7	57
8	143
9	253
10	483
11	1057
12	2071
13	4005
14	8235
15	16521
16	32543
17	65485
18	131571
19	261745
20	523687
21	1049973
22	2096955
23	4191705
24	8391599
25	16779421
26	33546243
27	67112641
28	134230327
29	268415301
30	536865867
31	1073787177

Then it occured to me that if you subtract one from that number, m divides the result if m is prime. This being the case for m=2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31 can hardly be a coincidence, so I subtracted 1 from the number and calculated the division.

Table 3.
m	(#E - 2)/2 - 1	((#E - 2)/2 - 1)/m
2	2	1
3	0	0
4	6
5	20	4
6	26
7	56	8
8	142
9	252
10	482
11	1056	96
12	2070
13	4004	308
14	8234
15	16520
16	32542
17	65484	3852
18	131570
19	261744	13776
20	523686
21	1049972
22	2096954
23	4191704	182248
24	8391598
25	16779420
26	33546242
27	67112640
28	134230326
29	268415300	9255700
30	536865866
31	1073787176	34638296

This isn't as odd as it might seem, it is our friend Frobenius again! The value $ x=1 $ gives rise to the '1' count; after all we have b=1 and thus Tr(x) = Tr(1/x) for x=1! And if some $x \neq 0$ and $x \neq 1$ satisfies Tr(x) = Tr(1/x), then the Frobenius map that sends $x \mapsto x^2$ gives a different value of x that satisfies the formula as well. Since Frobenius repeats after m times when m is prime, those values of x come in groups of size m.

This discovery therefore immediately clarifies how to continue. When m is not prime, some values of x will not repeat after applying Frobenius m times, but after a factor of m times. For example, if m = 12 then some values of x will repeat after applying Frobenius 2, 3, 4, or 6 times, because each of those values divides 12.

We can therefore write (#E - 2)/2 - 1 as a weighted sum over the divisors of m as follows,

$(\#E - 2)/2 - 1 = \sum_{1 \le d < m, d|m} w(m, d) \cdot m/d$

where w(m, d) is a function of the divisor and of the field (not of E since a=0 and b=1 are fixed and the whole elliptic curve is virtually out of the picture here). As the field is entirely determined by m, w(m, d) is a function of d and m. The actual value of w(m, d) is then the number of different elements x of the field $\mathbb{F}_{2^m}$ that satisfy Tr(x) = Tr(1/x) and for which the smallest positive integer n such that x^2ⁿ = x is n = m/d. Put in a formula,

$w(m, d) = \left|\left\{x \in \mathbb{F}_{2^m} \mid \mathrm{Tr}(x)=\mathrm{Tr}(1/x) \text{ and } \min \left\{k \in \mathbb{Z}^+ \mid x^{2^k} = x \right\} = m/d \right\}\right|$

These values can be brute force calculated. Note that when m is prime then ((#E - 2)/2 - 1)/m = w(m, 1), so we replace the last column in the previous table with w(m, 1). New columns are added for each of the divisors of m. The program used to calculate this can be found in testsuite/point/bspace.cc.

Table 4.
m	(#E - 2)/2 - 1	w(m, 1)	w(m, 2)	w(m, 3)	w(m, 4)	w(m, 5)	w(m, 6)	w(m, 7)	w(m, 8)	w(m, 9)	w(m, 10)	w(m, 11)	w(m, 12)	w(m, 13)	w(m, 14)	w(m, 15)
2	2	1
3	0	0
4	6	1	1
5	20	4
6	26	3	2	1
7	56	8
8	142	16	3		1
9	252	28		0
10	482	45	6			1
11	1056	96
12	2070	167	9	1	2		1
13	4004	308
14	8234	579	18					1
15	16520	1100		4		0
16	32542	2018	30		3				1
17	65484	3852
18	131570	7280	56	3			2			1
19	261744	13776
20	523686	26133	99		6	1					1
21	1049972	49996		8				0
22	2096954	95223	186									1
23	4191704	182248
24	8391598	349474	335	16	9		3		2				1
25	16779420	671176				4
26	33546242	1289925	630											1
27	67112640	2485644		28						0
28	134230326	4793355	1161		18			1							1
29	268415300	9255700
30	536865866	17894421	2182	45		3	6				2					1
31	1073787176	34638296

And what a beautiful structure it is! This shows clearly that only w(m, 1) and w(m, 2) are significant. The value of w(m, d) with d > 2 can be directly expressed in one of the former:

$w(m, d) = \begin{cases} w(m / d, 1) & \mbox{if d is odd} \\ w(2m / d, 2) & \mbox{if d is even} \end{cases}$

After several weeks of writing down little numbers of papers, I can tell you that got very excited when I finally found the next step: A way to calculate w(m, 2)!

$w(2m, 2) = foc(m)/m$

where

$foc(m) = 2^m - \sum_{0<d<m,\ d|m} foc(d)$

For example, in the table we see that w(26, 2) = 630. This number can be expressed in m as foc(13)/13 = (2¹³ - foc(1))/13 = (8192 - 2)/13 = 630.

The name foc stands for Frobenius Order Count, as it turns out that foc(m) is the number of elements of the field $\mathbb{F}_{2^m}$ for which the smallest positive integer n such that x^2ⁿ = x is n = m.

foc(1) therefore represents the two elements of the base field { 0, 1 } whose square is equal to itself and thus never contribute to the count of elements. While if m is prime, then every other element does contribute, hence that for prime m we have 2^m - 2. If m is not prime then elements with a Frobenius multiplicity between 1 and m have to be taken into account, by subtracting them, as well.

In order to really understand the table (and the meaning of w(m,d)), lets look at each of the different contributions in turn. We'll start with the diagonal series of 1's on the right-side of the table. These 1's each have a count of 2 (m/d = 2): there are two different values of x that contribute to each of them. The reason for their existance is that, for some fields, there exists an element x such that applying Frobenius two times returns to itself (x⁴ = x). If such an element exists, then apparently all of them satisfy the equation Tr(x) = Tr(1/x), which can only be accounted for when x² = 1/x (recall that Tr(x) = Tr(x²) due to Frobenius). "Normally" an element of $\mathbb{F}_{2^2}$ is expected to return to itself after applying Frobenius two times. Lets recall that fact by working it out.

Table 5.
F_2², t²+t+1=0
x			1/x			x²	x²+x+1
0						0	0
t⁰	=	1	t⁰	=	1	1	1
t¹	=	t	t²	=	t + 1	t + 1	0
t²	=	t + 1	t¹	=	t	t	0

Where the Frobenius multiplicity of t and t+1 is 2 because squaring t gives t+1 and squaring that once more gives t again.

The elements 0 and 1 have both already been taken into account by subtracting 2 from #E (for x = 0 and the point at infinity) and subtracting 1 from (#E - 2) / 2 respectively, so we don't see any count for them back in the table with w(m, d) (table 4). I won't show x = 0 in the table below and x = 1 will be dropped further on, too.

Looking at table 4 again, the table with w(m,d), we see that this 1 occurs for every even value of m. The reason for that is that each of those fields has $\mathbb{F}_{2^2}$ as subfield, and have therefore two elements that satisfy x² + x + 1 = 0. More in general, a field $\mathbb{F}_{2^m}$ will have a subfield $\mathbb{F}_{2^n}$ if and only if n|m. As an example lets have a detailed look at the smallest field that has $\mathbb{F}_{2^2}$ as subfield, $\mathbb{F}_{2^4}$ . Lets use g as generator of the field rather than t in order not to get confused by the previously used t for the reduction polynomial of $\mathbb{F}_{2^2}$ .

Table 6.
F_2⁴, t⁴+t+1=0, g=t
x			1/x			x²	x²+x+1
g⁰	=	1	g⁰	=	1	1	1
g¹	=	g	g¹⁴	=	g³ + 1	g²	g² + g + 1
g²	=	g²	g¹³	=	g³ + g² + 1	g + 1	g² + g
g³	=	g³	g¹²	=	g³ + g² + g + 1	g³ + g²	g² + 1
g⁴	=	g+1	g¹¹	=	g³ + g² + g	g² + 1	g² + g + 1
g⁵	=	g² + g	g¹⁰	=	g² + g + 1	g² + g + 1	0
g⁶	=	g³ + g²	g⁹	=	g³ + g	g³ + g² + g + 1	g
g⁷	=	g³ + g + 1	g⁸	=	g² + 1	g³ + 1	g + 1
g⁸	=	g² + 1	g⁷	=	g³ + g + 1	g	g² + g
g⁹	=	g³ + g	g⁶	=	g³ + g²	g³	g + 1
g¹⁰	=	g² + g + 1	g⁵	=	g² + g	g² + g	0
g¹¹	=	g³ + g² + g	g⁴	=	g+1	g³ + g + 1	g²
g¹²	=	g³ + g² + g + 1	g³	=	g³	g³ + g	g²
g¹³	=	g³ + g² + 1	g²	=	g²	g³ + g² + g	g
g¹⁴	=	g³ + 1	g¹	=	g	g³ + g² + 1	g² + 1

Here I used the same color for elements in the same Frobenius equivalence class. For example, g⁶ and g⁹ are in the same Frobenius equivalence class because ((g⁶)²)² = s²⁴ = g⁹ (recall that g^{2^m} = g and thus g¹⁵ = 1).

Note that the two values (g⁵ and g¹⁰) together with g⁰ form a group under multiplication isomorphic with $\mathbb{Z}_3$ , and together with 0 they form a group under addition, so that this latter set is a subfield isomorphic with $\mathbb{F}_4$ . For our investigation only the multiplication is important, so lets look at the group $\mathbb{Z}_3$ .

Table 7.
Z₃
n	2n
0	0
1	2
2	1

As mentioned before, a field $\mathbb{F}_{p^m}$ will only contain a subfield of the form $\mathbb{F}_{p^n}$ if n|m (so that (pⁿ - 1) divides (p^m - 1), giving a subgroup under multiplication with size (p^m - 1) / (pⁿ - 1) = p^m/n + 1). Therefore, every field with even m has a subgroup under multiplication isomorphic with $\mathbb{Z}_3$ that gives rise to the same number of solutions as does its subfield $\mathbb{F}_{2^2}$ . This is what caused the diagonal of 1's in the table for w(m, m/2).

Now lets have a look at the next diagonal, the alternating 2's and 0's, in particular the 2's thereof. These are the contributions w(m, m/3) and in particular when m is even. The smallest subfield that we can investigate that has this structure is with m = 6 and thus d = m/3 = 2. The following table was generated with testsuite/point/bspacetables2.cc.

Table 8.
F_2⁶, t⁶+t+1=0
x = gⁿ			GCD(n, 63)	1/x			Tr(x)	Tr(1/x)	d	x²+x+1	x³+x+1
g¹	=	t	1	g⁶²	=	t⁵+1	0	1	1	t²+t+1	t³+t+1
g²	=	t²	1	g⁶¹	=	t⁵+t⁴+1	0	1	1	t⁴+t²+1	t²+t
g³	=	t³	3	g⁶⁰	=	t⁵+t⁴+t³+1	0	1	1	t³+t	t⁴+1
g⁴	=	t⁴	1	g⁵⁹	=	t⁵+t⁴+t³+t²+1	0	1	1	t⁴+t³+t²+1	t⁴+t²
g⁵	=	t⁵	1	g⁵⁸	=	t⁵+t⁴+t³+t²+t+1	1	1	1	t⁴+1	t³+1
g⁶	=	t+1	3	g⁵⁷	=	t⁵+t⁴+t³+t²+t	0	1	1	t²+t+1	t³+t²+1
g⁷	=	t²+t	7	g⁵⁶	=	t⁴+t³+t²+t+1	0	0	1	t⁴+t+1	t⁵+t⁴+t³+t²
g⁸	=	t³+t²	1	g⁵⁵	=	t⁵+t³+t²+t	0	1	1	t⁴+t³+t²+t	t⁴+t³+t²
g⁹	=	t⁴+t³	9	g⁵⁴	=	t⁴+t²+t+1	0	0	2	t⁴+t²+t	t⁴+t²+t+1
g¹⁰	=	t⁵+t⁴	1	g⁵³	=	t⁵+t³+t	1	1	1	t³+t²+1	t
g¹¹	=	t⁵+t+1	1	g⁵²	=	t⁴+t²+1	1	0	1	t⁴+t²+t+1	t⁵+t⁴
g¹²	=	t²+1	3	g⁵¹	=	t⁵+t³+t+1	0	1	1	t⁴+t²+1	t⁴+t
g¹³	=	t³+t	1	g⁵⁰	=	t⁵+t⁴+t²	0	1	1	t³+t²	t⁵+t⁴+t³+t²+1
g¹⁴	=	t⁴+t²	7	g⁴⁹	=	t⁴+t³+t	0	0	1	t³+1	t⁵+t³+t²+t+1
g¹⁵	=	t⁵+t³	3	g⁴⁸	=	t³+t²+1	1	0	1	t⁴+t³+t	t⁵+t⁴
g¹⁶	=	t⁴+t+1	1	g⁴⁷	=	t⁵+t²+t+1	0	1	1	t⁴+t³+t+1	t⁴+t³+t²+t+1
g¹⁷	=	t⁵+t²+t	1	g⁴⁶	=	t⁵+t⁴+t	1	1	1	t+1	t³+t²
g¹⁸	=	t³+t²+t+1	9	g⁴⁵	=	t⁴+t³+1	0	0	2	t⁴+t³	t⁴+t³+1
g¹⁹	=	t⁴+t³+t²+t	1	g⁴⁴	=	t⁵+t³+t²+1	0	1	1	t²	t⁵+1
g²⁰	=	t⁵+t⁴+t³+t²	1	g⁴³	=	t⁵+t⁴+t²+t+1	1	1	1	t⁴+t	t²
g²¹	=	t⁵+t⁴+t³+t+1	21	g⁴²	=	t⁵+t⁴+t³+t	1	1	3	0	t⁵+t⁴+t³+t+1
g²²	=	t⁵+t⁴+t²+1	1	g⁴¹	=	t⁴+t³+t²+1	1	0	1	t⁴+t³+1	t⁵+t⁴+t³+t²
g²³	=	t⁵+t³+1	1	g⁴⁰	=	t⁵+t³+t²+t+1	1	1	1	t⁴+t³+t	t⁵+t³+t+1
g²⁴	=	t⁴+1	3	g³⁹	=	t⁵+t⁴+t²+t	0	1	1	t⁴+t³+t²+1	t³
g²⁵	=	t⁵+t	1	g³⁸	=	t⁴+t³+t+1	1	0	1	t⁴+t²+t+1	t⁵+t²+t
g²⁶	=	t²+t+1	1	g³⁷	=	t⁵+t³+t²	0	1	1	t⁴+t+1	t⁵+t³+t²+t
g²⁷	=	t³+t²+t	9	g³⁶	=	t⁴+t²+t	0	0	2	t⁴+t³	0
g²⁸	=	t⁴+t³+t²	7	g³⁵	=	t³+t+1	0	0	1	t	t⁵+t²+t
g²⁹	=	t⁵+t⁴+t³	1	g³⁴	=	t⁵+t²	1	1	1	t²+t	t⁵+t³
g³⁰	=	t⁵+t⁴+t+1	3	g³³	=	t⁴+t	1	0	1	t³+t+1	t⁵+t⁴+t³+t²
g³¹	=	t⁵+t²+1	1	g³²	=	t³+1	1	0	1	t²+1	t⁴+t²+t+1
g³²	=	t³+1	1	g³¹	=	t⁵+t²+1	0	1	1	t³+t	t⁴+t³+t
g³³	=	t⁴+t	3	g³⁰	=	t⁵+t⁴+t+1	0	1	1	t⁴+t³+t+1	t²+1
g³⁴	=	t⁵+t²	1	g²⁹	=	t⁵+t⁴+t³	1	1	1	t²+1	t⁴+t+1
g³⁵	=	t³+t+1	7	g²⁸	=	t⁴+t³+t²	0	0	1	t³+t²	t⁵+t⁴
g³⁶	=	t⁴+t²+t	9	g²⁷	=	t³+t²+t	0	0	2	t³+t²+t+1	t³+t²+t
g³⁷	=	t⁵+t³+t²	1	g²⁶	=	t²+t+1	1	0	1	t³+t²+t	t⁵
g³⁸	=	t⁴+t³+t+1	1	g²⁵	=	t⁵+t	0	1	1	t⁴	t⁵+t⁴+1
g³⁹	=	t⁵+t⁴+t²+t	3	g²⁴	=	t⁴+1	1	0	1	t⁴+t³+t²+t+1	t⁵
g⁴⁰	=	t⁵+t³+t²+t+1	1	g²³	=	t⁵+t³+1	1	1	1	t³	t⁴
g⁴¹	=	t⁴+t³+t²+1	1	g²²	=	t⁵+t⁴+t²+1	0	1	1	t	t⁵+t²+1
g⁴²	=	t⁵+t⁴+t³+t	21	g²¹	=	t⁵+t⁴+t³+t+1	1	1	3	0	t⁵+t⁴+t³+t
g⁴³	=	t⁵+t⁴+t²+t+1	1	g²⁰	=	t⁵+t⁴+t³+t²	1	1	1	t⁴+t³+t²+t+1	t⁵+t⁴+t³+t²+t
g⁴⁴	=	t⁵+t³+t²+1	1	g¹⁹	=	t⁴+t³+t²+t	1	0	1	t³+t²+t	t⁵+t³+t²+t+1
g⁴⁵	=	t⁴+t³+1	9	g¹⁸	=	t³+t²+t+1	0	0	2	t⁴+t²+t	0
g⁴⁶	=	t⁵+t⁴+t	1	g¹⁷	=	t⁵+t²+t	1	1	1	t³+t+1	t⁵+t⁴+t²+t
g⁴⁷	=	t⁵+t²+t+1	1	g¹⁶	=	t⁴+t+1	1	0	1	t+1	t³+t²+t
g⁴⁸	=	t³+t²+1	3	g¹⁵	=	t⁵+t³	0	1	1	t⁴+t³+t²+t	t+1
g⁴⁹	=	t⁴+t³+t	7	g¹⁴	=	t⁴+t²	0	0	1	t⁴	t⁵
g⁵⁰	=	t⁵+t⁴+t²	1	g¹³	=	t³+t	1	0	1	t⁴+t³+1	t⁵+t²
g⁵¹	=	t⁵+t³+t+1	3	g¹²	=	t²+1	1	0	1	t⁴+t³+t²	t⁵+t²
g⁵²	=	t⁴+t²+1	1	g¹¹	=	t⁵+t+1	0	1	1	t³+1	t⁵+t²+t+1
g⁵³	=	t⁵+t³+t	1	g¹⁰	=	t⁵+t⁴	1	1	1	t⁴+t³+t²	t⁵+t⁴+t³+1
g⁵⁴	=	t⁴+t²+t+1	9	g⁹	=	t⁴+t³	0	0	2	t³+t²+t+1	0
g⁵⁵	=	t⁵+t³+t²+t	1	g⁸	=	t³+t²	1	0	1	t³	t⁴+t³+1
g⁵⁶	=	t⁴+t³+t²+t+1	7	g⁷	=	t²+t	0	0	1	t²	t⁵+t²
g⁵⁷	=	t⁵+t⁴+t³+t²+t	3	g⁶	=	t+1	1	0	1	t⁴+t²	t⁵+t²+t
g⁵⁸	=	t⁵+t⁴+t³+t²+t+1	1	g⁵	=	t⁵	1	1	1	t⁴+t²	t⁵+t⁴+t+1
g⁵⁹	=	t⁵+t⁴+t³+t²+1	1	g⁴	=	t⁴	1	0	1	t⁴+t	t⁴+t²+t+1
g⁶⁰	=	t⁵+t⁴+t³+1	3	g³	=	t³	1	0	1	t²+t	t⁵+t³+t²+t+1
g⁶¹	=	t⁵+t⁴+1	1	g²	=	t²	1	0	1	t³+t²+1	t³+t²+t
g⁶²	=	t⁵+1	1	g¹	=	t	1	0	1	t⁴+1	t⁴+t³+1

Here we see again the two elements that give rise to the w(6,3) as g²¹ and g⁴². Together with 1 they form the multiplicative subgroup GF(2²)^* as can be seen from the fact that x²+x+1 in the second column from the right is zero. Likewise, the third column contains zeroes for the roots of x³+x+1: g²⁷, g⁴⁵ and g⁵⁴ which are thus, elements of the multiplicative group GF(2³)^*. The remaining elements of that group, besides the multiplicative unity, are g⁹, g¹⁸ and g³⁶. At this point I have no idea if it's a coincidence that those are precisely the inverse of first three (this could be because there simply are no other elements with GCD(n, 63) of 9). Note that GF(2³)^* is isomorphic with $\mathbb{Z}_7$ :

Table 9.
Z₇
n	6n
0	0
1	6
2	5
3	4
4	3
5	2
6	1

In this case we have two different colors (two Frobenius equivalence classes) and thus w(6, 2) = 2.

Looking at F_2⁶ again, we only see one other (besides { g²¹, g⁴² }}) Frobenius equivalence class that automatically adds to the count of solutions in the form of the elements { t⁷, t¹⁴, t²⁸, t³⁵, t⁴⁹, t⁵⁶ }, because their inverses are in the same Frobenius equivalence class. These elements added one to the value of w(6,1) because there are six of them (d = 1).

What exactly is the structure that gives rise to these six elements? As you can see, they are not part of a subfield of $\mathbb{F}_{2^6}$ ( $\mathbb{F}_{2^2}$ and $\mathbb{F}_{2^3}$ ): neither of the two right-most columns is zero for these elements.

The magic lies in the fact that each element can be paired up with another element from the same Frobenius equivalence class, such that if x is in this class then so is 1/x. The factor 7 is an arbitrary residue factor so lets start with deviding that away. Much in the same way as we did get $\mathbb{Z}_7$ before, now we get $\mathbb{Z}_9$ . The elements we have are the set $S = \{ 1, 2, 4, 8, 16-9 = 7, 32-27 = 5 \} = \{ 2^i \pmod{9} \mid i \in \mathbb{N} \}$ which is a direct result of the fact that we repeatedly applied Frobenius: each time the exponents of t are doubled.

The puzzle that we have to solve therefore is this: Let G = Z/nZ, S={2ⁱ}, when will S be even and for each x in S there will be a y in S such that x+y = 0 (mod n)?

I had two mathematicians look at that, and after two hours of trying and discussion, they came up with the following. If there exists a k such that 2^k + 1 = 0 (mod n), then let k be the least positive such, then S = { 2⁰, 2¹, ..., 2^(2k-1)} since 2^2k = 1 (mod n), thus S = 2k is even, and 2ⁱ + 2^k+i = 2ⁱ + (-1) $\cdot$ 2ⁱ = 0 (mod n), i.e. all elements are paired up. Let 2ⁱ = x in S then there exists a y in S such that x + y = 0 (mod n) thus 2ⁱ + 2^k $\cdot$ 2ⁱ = 0 (mod n), thus 2^k $\cdot$ 2ⁱ = (-1) $\cdot$ 2ⁱ (mod n), which shows that this is the only possibility. $\qed$

The restriction on the factor (n) is therefore that there has to exist a k such that 2^k + 1 = 0 (mod n).

And indeed, 9 = 2³ + 1, where the exponent k = 3 gives rise to 2k = 6 elements in the Frobenius equivalence class of w(m, m/6). Moreover, 3 = 2¹ + 1, where the exponent k = 1 gives rise to 2k = 2 elements in the Frobenius equivalence class of w(m, m/2). This does not happen for every m however, but only for those m where 2^m - 1 has a factor n such that there exists a positive k such that 2^k + 1 = 0 (mod n).

Lets start using m/d rather than d, because it is m/d that is constant along of the diagonals in table 4. For the same reason, show (2^m - 1) / gcd(2^m - 1, n) instead of gcd(2^m - 1, n).

The same structures return for larger m if it is a multiple of 6. Consider these tables for m = 6, 12, 18, 24:

Table 10-a.
F_2⁶, t⁶+t+1=0
x = gⁿ			63/GCD(n, 63)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g⁹	=	t⁴+t³	7	g⁵⁴	=	t⁴+t²+t+1	0	0	3	t⁴+t²+t	t⁴+t²+t+1
g¹⁸	=	t³+t²+t+1	7	g⁴⁵	=	t⁴+t³+1	0	0	3	t⁴+t³	t⁴+t³+1
g²¹	=	t⁵+t⁴+t³+t+1	3	g⁴²	=	t⁵+t⁴+t³+t	1	1	2	0	t⁵+t⁴+t³+t+1
g²⁷	=	t³+t²+t	7	g³⁶	=	t⁴+t²+t	0	0	3	t⁴+t³	0
g³⁶	=	t⁴+t²+t	7	g²⁷	=	t³+t²+t	0	0	3	t³+t²+t+1	t³+t²+t
g⁴²	=	t⁵+t⁴+t³+t	3	g²¹	=	t⁵+t⁴+t³+t+1	1	1	2	0	t⁵+t⁴+t³+t
g⁴⁵	=	t⁴+t³+1	7	g¹⁸	=	t³+t²+t+1	0	0	3	t⁴+t²+t	0
g⁵⁴	=	t⁴+t²+t+1	7	g⁹	=	t⁴+t³	0	0	3	t³+t²+t+1	0

Table 10-b.
F_2¹², t¹²+t³+1=0
x = gⁿ			4095/GCD(n, 4095)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g⁵⁸⁵	=	t¹⁰+t⁷+t⁵+t+1	7	g³⁵¹⁰	=	t¹¹+t⁸+t⁷+t	0	0	3	t¹¹+t⁸+t⁷+t+1	t¹¹+t⁸+t⁷+t
g¹¹⁷⁰	=	t¹¹+t¹⁰+t⁸+t⁵+1	7	g²⁹²⁵	=	t¹⁰+t⁷+t⁵+t	0	0	3	t¹⁰+t⁷+t⁵+t+1	t¹⁰+t⁷+t⁵+t
g¹³⁶⁵	=	t⁶+t³	3	g²⁷³⁰	=	t⁶+t³+1	0	0	2	0	t⁶+t³
g¹⁷⁵⁵	=	t¹¹+t¹⁰+t⁸+t⁵	7	g²³⁴⁰	=	t¹¹+t⁸+t⁷+t+1	0	0	3	t¹⁰+t⁷+t⁵+t+1	0
g²³⁴⁰	=	t¹¹+t⁸+t⁷+t+1	7	g¹⁷⁵⁵	=	t¹¹+t¹⁰+t⁸+t⁵	0	0	3	t¹¹+t¹⁰+t⁸+t⁵+1	t¹¹+t¹⁰+t⁸+t⁵
g²⁷³⁰	=	t⁶+t³+1	3	g¹³⁶⁵	=	t⁶+t³	0	0	2	0	t⁶+t³+1
g²⁹²⁵	=	t¹⁰+t⁷+t⁵+t	7	g¹¹⁷⁰	=	t¹¹+t¹⁰+t⁸+t⁵+1	0	0	3	t¹¹+t⁸+t⁷+t+1	0
g³⁵¹⁰	=	t¹¹+t⁸+t⁷+t	7	g⁵⁸⁵	=	t¹⁰+t⁷+t⁵+t+1	0	0	3	t¹¹+t¹⁰+t⁸+t⁵+1	0

Table 10-c.
F_2¹⁸, t¹⁸+t³+1=0
x = gⁿ			262143/GCD(n, 262143)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g³⁷⁴⁴⁹	=	t¹²+t⁶+t³+1	7	g²²⁴⁶⁹⁴	=	t¹²+t⁹	0	0	3	t⁹+t⁶+t³+1	0
g⁷⁴⁸⁹⁸	=	t¹²+t⁹+1	7	g¹⁸⁷²⁴⁵	=	t⁹+t⁶+t³+1	0	0	3	t¹²+t⁶+t³	0
g⁸⁷³⁸¹	=	t¹⁵+t¹²+t⁹+t³+1	3	g¹⁷⁴⁷⁶²	=	t¹⁵+t¹²+t⁹+t³	1	1	2	0	t¹⁵+t¹²+t⁹+t³+1
g¹¹²³⁴⁷	=	t¹²+t⁶+t³	7	g¹⁴⁹⁷⁹⁶	=	t⁹+t⁶+t³	0	0	3	t⁹+t⁶+t³+1	t⁹+t⁶+t³
g¹⁴⁹⁷⁹⁶	=	t⁹+t⁶+t³	7	g¹¹²³⁴⁷	=	t¹²+t⁶+t³	0	0	3	t¹²+t⁹	0
g¹⁷⁴⁷⁶²	=	t¹⁵+t¹²+t⁹+t³	3	g⁸⁷³⁸¹	=	t¹⁵+t¹²+t⁹+t³+1	1	1	2	0	t¹⁵+t¹²+t⁹+t³
g¹⁸⁷²⁴⁵	=	t⁹+t⁶+t³+1	7	g⁷⁴⁸⁹⁸	=	t¹²+t⁹+1	0	0	3	t¹²+t⁹	t¹²+t⁹+1
g²²⁴⁶⁹⁴	=	t¹²+t⁹	7	g³⁷⁴⁴⁹	=	t¹²+t⁶+t³+1	0	0	3	t¹²+t⁶+t³	t¹²+t⁶+t³+1

Table 10-d.
F_2²⁴, t²⁴+t⁴+t³+t+1=0
x = gⁿ			16777215/GCD(n, 16777215)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g^2396745	=	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²+1	7	g^14380470	=	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵	0	0	3	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵+1	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵
g^4793490	=	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²+1	7	g^11983725	=	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²	0	0	3	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²+1	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²
g^5592405	=	t¹²+t⁶+t³+t²+t	3	g^11184810	=	t¹²+t⁶+t³+t²+t+1	0	0	2	0	t¹²+t⁶+t³+t²+t
g^7190235	=	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²	7	g^9586980	=	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵+1	0	0	3	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²+1	0
g^9586980	=	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵+1	7	g^7190235	=	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²	0	0	3	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²+1	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²
g^11184810	=	t¹²+t⁶+t³+t²+t+1	3	g^5592405	=	t¹²+t⁶+t³+t²+t	0	0	2	0	t¹²+t⁶+t³+t²+t+1
g^11983725	=	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²	7	g^4793490	=	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²+1	0	0	3	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵+1	0
g^14380470	=	t¹⁸+t¹⁵+t¹³+t⁸+t⁷+t⁶+t⁵	7	g^2396745	=	t¹⁵+t¹⁴+t¹³+t⁹+t⁷+t⁵+t³+t²+1	0	0	3	t¹⁸+t¹⁴+t⁹+t⁸+t⁶+t³+t²+1	0

showing all the elements that contribute to w(m, m/2) and w(m, m/3), namely one Frobenius equivalence class for m/2, and two Frobenius equivalence classes for m/3. If m is an odd multiple of 3, the same two Frobenius equivalence classes still exist, but they are not a solution of the Elliptic Curve (Tr(x) $\neq$ Tr(1/x)):

Table 11-a.
F_2³, t³+t+1=0
x = gⁿ			7/GCD(n, 7)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g¹	=	t	7	g⁶	=	t²+1	0	1	3	t²+t+1	0
g²	=	t²	7	g⁵	=	t²+t+1	0	1	3	t+1	0
g³	=	t+1	7	g⁴	=	t²+t	1	0	3	t²+t+1	t²+t
g⁴	=	t²+t	7	g³	=	t+1	0	1	3	t²+1	0
g⁵	=	t²+t+1	7	g²	=	t²	1	0	3	t²+1	t²
g⁶	=	t²+1	7	g¹	=	t	1	0	3	t+1	t

Table 11-b.
F_2⁹, t⁹+t+1=0
x = gⁿ			511/GCD(n, 511)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g⁷³	=	t⁸+t⁷+t⁶+t⁴+t+1	7	g⁴³⁸	=	t⁸+t⁵+t³+t²+t	1	0	3	t⁸+t⁵+t³+t²+t+1	t⁸+t⁵+t³+t²+t
g¹⁴⁶	=	t⁷+t⁶+t⁵+t⁴+t³+t²+1	7	g³⁶⁵	=	t⁸+t⁷+t⁶+t⁴+t	1	0	3	t⁸+t⁷+t⁶+t⁴+t+1	t⁸+t⁷+t⁶+t⁴+t
g²¹⁹	=	t⁷+t⁶+t⁵+t⁴+t³+t²	7	g²⁹²	=	t⁸+t⁵+t³+t²+t+1	0	1	3	t⁸+t⁷+t⁶+t⁴+t+1	0
g²⁹²	=	t⁸+t⁵+t³+t²+t+1	7	g²¹⁹	=	t⁷+t⁶+t⁵+t⁴+t³+t²	1	0	3	t⁷+t⁶+t⁵+t⁴+t³+t²+1	t⁷+t⁶+t⁵+t⁴+t³+t²
g³⁶⁵	=	t⁸+t⁷+t⁶+t⁴+t	7	g¹⁴⁶	=	t⁷+t⁶+t⁵+t⁴+t³+t²+1	0	1	3	t⁸+t⁵+t³+t²+t+1	0
g⁴³⁸	=	t⁸+t⁵+t³+t²+t	7	g⁷³	=	t⁸+t⁷+t⁶+t⁴+t+1	0	1	3	t⁷+t⁶+t⁵+t⁴+t³+t²+1	0

Table 11-c.
F_2¹⁵, t¹⁵+t+1=0
x = gⁿ			32767/GCD(n, 32767)	1/x			Tr(x)	Tr(1/x)	m/d	x²+x+1	x³+x+1
g⁴⁶⁸¹	=	t¹²+t¹⁰+t⁹+t⁵+t⁴+t	7	g²⁸⁰⁸⁶	=	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²+1	0	1	3	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t+1	0
g⁹³⁶²	=	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²	7	g²³⁴⁰⁵	=	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t+1	0	1	3	t¹²+t¹⁰+t⁹+t⁵+t⁴+t+1	0
g¹⁴⁰⁴³	=	t¹²+t¹⁰+t⁹+t⁵+t⁴+t+1	7	g¹⁸⁷²⁴	=	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t	1	0	3	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t+1	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t
g¹⁸⁷²⁴	=	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t	7	g¹⁴⁰⁴³	=	t¹²+t¹⁰+t⁹+t⁵+t⁴+t+1	0	1	3	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²+1	0
g²³⁴⁰⁵	=	t¹²+t¹⁰+t⁸+t⁶+t³+t²+t+1	7	g⁹³⁶²	=	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²	1	0	3	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²+1	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²
g²⁸⁰⁸⁶	=	t⁹+t⁸+t⁶+t⁵+t⁴+t³+t²+1	7	g⁴⁶⁸¹	=	t¹²+t¹⁰+t⁹+t⁵+t⁴+t	1	0	3	t¹²+t¹⁰+t⁹+t⁵+t⁴+t+1	t¹²+t¹⁰+t⁹+t⁵+t⁴+t

The following is a discussion of the data on this page.

It is not a coincidence that every time this shows alternating a table where every entry is a solution of the elliptic curve. For those tables where m / (m/d) is even, in other words, showing the elements that contribute to even d. We saw already before that those values, the values of w(m, 2), can be easily calculated.

Recall that,

$Tr(x) = \sum_{i=0}^{m-1}{x^{2^i}}$

In this case we have x = gⁿ such that (gⁿ)^{2^m/d} = gⁿ (= (gⁿ)^2⁰), and thus,

$Tr(x) = \sum_{i=0}^{m-1}{(g^n)^{2^i}} = \sum_{i=0}^{m-1}{(g^n)^{2^{(i\textrm{ mod }(m/d))}}} = d \sum_{i=0}^{m/d-1}{(g^n)^{2^i}} = 0$

where the last equation holds because d is even. Likewise Tr(1/x) = 0 and thus all values are a solution of the Elliptic curve.

Instead we need to concentrate on the other values, the odd values of d, and because the structures are 100% equivalent, it is also not needed to look at large m, the smallest with d = 1 will do, because the rest is trivially deducable.

Those elements are:

Table 15-a.
F_2³, t³+t+1=0
x = gⁿ			7/GCD(n, 7)	1/x			Tr(x)	Tr(1/x)	m/d
g¹	=	t	7	g⁶	=	t²+1	0	1	3
g²	=	t²	7	g⁵	=	t²+t+1	0	1	3
g³	=	t+1	7	g⁴	=	t²+t	1	0	3
g⁴	=	t²+t	7	g³	=	t+1	0	1	3
g⁵	=	t²+t+1	7	g²	=	t²	1	0	3
g⁶	=	t²+1	7	g¹	=	t	1	0	3

Table 15-b.
F_2⁴, t⁴+t+1=0
x = gⁿ			15/GCD(n, 15)	1/x			Tr(x)	Tr(1/x)	m/d
g¹	=	t	15	g¹⁴	=	t³+1	0	1	4
g²	=	t²	15	g¹³	=	t³+t²+1	0	1	4
g³	=	t³	5	g¹²	=	t³+t²+t+1	1	1	4
g⁴	=	t+1	15	g¹¹	=	t³+t²+t	0	1	4
g⁶	=	t³+t²	5	g⁹	=	t³+t	1	1	4
g⁷	=	t³+t+1	15	g⁸	=	t²+1	1	0	4
g⁸	=	t²+1	15	g⁷	=	t³+t+1	0	1	4
g⁹	=	t³+t	5	g⁶	=	t³+t²	1	1	4
g¹¹	=	t³+t²+t	15	g⁴	=	t+1	1	0	4
g¹²	=	t³+t²+t+1	5	g³	=	t³	1	1	4
g¹³	=	t³+t²+1	15	g²	=	t²	1	0	4
g¹⁴	=	t³+1	15	g¹	=	t	1	0	4

Table 15-c.
F_2⁵, t⁵+t²+1=0
x = gⁿ			31/GCD(n, 31)	1/x			Tr(x)	Tr(1/x)	m/d
g¹	=	t	31	g³⁰	=	t⁴+t	0	0	5
g²	=	t²	31	g²⁹	=	t³+1	0	0	5
g³	=	t³	31	g²⁸	=	t⁴+t²+t	1	0	5
g⁴	=	t⁴	31	g²⁷	=	t³+t+1	0	0	5
g⁵	=	t²+1	31	g²⁶	=	t⁴+t²+t+1	1	1	5
g⁶	=	t³+t	31	g²⁵	=	t⁴+t³+1	1	0	5
g⁷	=	t⁴+t²	31	g²⁴	=	t⁴+t³+t²+t	0	1	5
g⁸	=	t³+t²+1	31	g²³	=	t³+t²+t+1	0	0	5
g⁹	=	t⁴+t³+t	31	g²²	=	t⁴+t²+1	1	1	5
g¹⁰	=	t⁴+1	31	g²¹	=	t⁴+t³	1	1	5
g¹¹	=	t²+t+1	31	g²⁰	=	t³+t²	1	1	5
g¹²	=	t³+t²+t	31	g¹⁹	=	t²+t	1	0	5
g¹³	=	t⁴+t³+t²	31	g¹⁸	=	t+1	1	1	5
g¹⁴	=	t⁴+t³+t²+1	31	g¹⁷	=	t⁴+t+1	0	1	5
g¹⁵	=	t⁴+t³+t²+t+1	31	g¹⁶	=	t⁴+t³+t+1	0	0	5
g¹⁶	=	t⁴+t³+t+1	31	g¹⁵	=	t⁴+t³+t²+t+1	0	0	5
g¹⁷	=	t⁴+t+1	31	g¹⁴	=	t⁴+t³+t²+1	1	0	5
g¹⁸	=	t+1	31	g¹³	=	t⁴+t³+t²	1	1	5
g¹⁹	=	t²+t	31	g¹²	=	t³+t²+t	0	1	5
g²⁰	=	t³+t²	31	g¹¹	=	t²+t+1	1	1	5
g²¹	=	t⁴+t³	31	g¹⁰	=	t⁴+1	1	1	5
g²²	=	t⁴+t²+1	31	g⁹	=	t⁴+t³+t	1	1	5
g²³	=	t³+t²+t+1	31	g⁸	=	t³+t²+1	0	0	5
g²⁴	=	t⁴+t³+t²+t	31	g⁷	=	t⁴+t²	1	0	5
g²⁵	=	t⁴+t³+1	31	g⁶	=	t³+t	0	1	5
g²⁶	=	t⁴+t²+t+1	31	g⁵	=	t²+1	1	1	5
g²⁷	=	t³+t+1	31	g⁴	=	t⁴	0	0	5
g²⁸	=	t⁴+t²+t	31	g³	=	t³	0	1	5
g²⁹	=	t³+1	31	g²	=	t²	0	0	5
g³⁰	=	t⁴+t	31	g¹	=	t	0	0	5

Table 15-d.
F_2⁶, t⁶+t+1=0
x = gⁿ			63/GCD(n, 63)	1/x			Tr(x)	Tr(1/x)	m/d
g¹	=	t	63	g⁶²	=	t⁵+1	0	1	6
g²	=	t²	63	g⁶¹	=	t⁵+t⁴+1	0	1	6
g³	=	t³	21	g⁶⁰	=	t⁵+t⁴+t³+1	0	1	6
g⁴	=	t⁴	63	g⁵⁹	=	t⁵+t⁴+t³+t²+1	0	1	6
g⁵	=	t⁵	63	g⁵⁸	=	t⁵+t⁴+t³+t²+t+1	1	1	6
g⁶	=	t+1	21	g⁵⁷	=	t⁵+t⁴+t³+t²+t	0	1	6
g⁷	=	t²+t	9	g⁵⁶	=	t⁴+t³+t²+t+1	0	0	6
g⁸	=	t³+t²	63	g⁵⁵	=	t⁵+t³+t²+t	0	1	6
g¹⁰	=	t⁵+t⁴	63	g⁵³	=	t⁵+t³+t	1	1	6
g¹¹	=	t⁵+t+1	63	g⁵²	=	t⁴+t²+1	1	0	6
g¹²	=	t²+1	21	g⁵¹	=	t⁵+t³+t+1	0	1	6
g¹³	=	t³+t	63	g⁵⁰	=	t⁵+t⁴+t²	0	1	6
g¹⁴	=	t⁴+t²	9	g⁴⁹	=	t⁴+t³+t	0	0	6
g¹⁵	=	t⁵+t³	21	g⁴⁸	=	t³+t²+1	1	0	6
g¹⁶	=	t⁴+t+1	63	g⁴⁷	=	t⁵+t²+t+1	0	1	6
g¹⁷	=	t⁵+t²+t	63	g⁴⁶	=	t⁵+t⁴+t	1	1	6
g¹⁹	=	t⁴+t³+t²+t	63	g⁴⁴	=	t⁵+t³+t²+1	0	1	6
g²⁰	=	t⁵+t⁴+t³+t²	63	g⁴³	=	t⁵+t⁴+t²+t+1	1	1	6
g²²	=	t⁵+t⁴+t²+1	63	g⁴¹	=	t⁴+t³+t²+1	1	0	6
g²³	=	t⁵+t³+1	63	g⁴⁰	=	t⁵+t³+t²+t+1	1	1	6
g²⁴	=	t⁴+1	21	g³⁹	=	t⁵+t⁴+t²+t	0	1	6
g²⁵	=	t⁵+t	63	g³⁸	=	t⁴+t³+t+1	1	0	6
g²⁶	=	t²+t+1	63	g³⁷	=	t⁵+t³+t²	0	1	6
g²⁸	=	t⁴+t³+t²	9	g³⁵	=	t³+t+1	0	0	6
g²⁹	=	t⁵+t⁴+t³	63	g³⁴	=	t⁵+t²	1	1	6
g³⁰	=	t⁵+t⁴+t+1	21	g³³	=	t⁴+t	1	0	6
g³¹	=	t⁵+t²+1	63	g³²	=	t³+1	1	0	6
g³²	=	t³+1	63	g³¹	=	t⁵+t²+1	0	1	6
g³³	=	t⁴+t	21	g³⁰	=	t⁵+t⁴+t+1	0	1	6
g³⁴	=	t⁵+t²	63	g²⁹	=	t⁵+t⁴+t³	1	1	6
g³⁵	=	t³+t+1	9	g²⁸	=	t⁴+t³+t²	0	0	6
g³⁷	=	t⁵+t³+t²	63	g²⁶	=	t²+t+1	1	0	6
g³⁸	=	t⁴+t³+t+1	63	g²⁵	=	t⁵+t	0	1	6
g³⁹	=	t⁵+t⁴+t²+t	21	g²⁴	=	t⁴+1	1	0	6
g⁴⁰	=	t⁵+t³+t²+t+1	63	g²³	=	t⁵+t³+1	1	1	6
g⁴¹	=	t⁴+t³+t²+1	63	g²²	=	t⁵+t⁴+t²+1	0	1	6
g⁴³	=	t⁵+t⁴+t²+t+1	63	g²⁰	=	t⁵+t⁴+t³+t²	1	1	6
g⁴⁴	=	t⁵+t³+t²+1	63	g¹⁹	=	t⁴+t³+t²+t	1	0	6
g⁴⁶	=	t⁵+t⁴+t	63	g¹⁷	=	t⁵+t²+t	1	1	6
g⁴⁷	=	t⁵+t²+t+1	63	g¹⁶	=	t⁴+t+1	1	0	6
g⁴⁸	=	t³+t²+1	21	g¹⁵	=	t⁵+t³	0	1	6
g⁴⁹	=	t⁴+t³+t	9	g¹⁴	=	t⁴+t²	0	0	6
g⁵⁰	=	t⁵+t⁴+t²	63	g¹³	=	t³+t	1	0	6
g⁵¹	=	t⁵+t³+t+1	21	g¹²	=	t²+1	1	0	6
g⁵²	=	t⁴+t²+1	63	g¹¹	=	t⁵+t+1	0	1	6
g⁵³	=	t⁵+t³+t	63	g¹⁰	=	t⁵+t⁴	1	1	6
g⁵⁵	=	t⁵+t³+t²+t	63	g⁸	=	t³+t²	1	0	6
g⁵⁶	=	t⁴+t³+t²+t+1	9	g⁷	=	t²+t	0	0	6
g⁵⁷	=	t⁵+t⁴+t³+t²+t	21	g⁶	=	t+1	1	0	6
g⁵⁸	=	t⁵+t⁴+t³+t²+t+1	63	g⁵	=	t⁵	1	1	6
g⁵⁹	=	t⁵+t⁴+t³+t²+1	63	g⁴	=	t⁴	1	0	6
g⁶⁰	=	t⁵+t⁴+t³+1	21	g³	=	t³	1	0	6
g⁶¹	=	t⁵+t⁴+1	63	g²	=	t²	1	0	6
g⁶²	=	t⁵+1	63	g¹	=	t	1	0	6

The tables are still larger than needed: all of the elements in a Frobenius equivalence class are equivalent. Instead of showing m elements with the same color, we might as well put them all in one entry.

In the tables below, a { 1, 2, 4 } means the elements g, g² and g⁴.

Table 16-a.
F_2³, t³+t+1=0, g=t²
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4}	0	{ 3, 5, 6}	1

Table 16-b.
F_2⁴, t⁴+t+1=0, g=t
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4, 8}	0	{ 7, 11, 13, 14}	1
{ 3, 6, 9, 12}	1	{ 3, 6, 9, 12}	1

Table 16-c.
F_2⁵, t⁵+t²+1=0, g=t²
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4, 8, 16}	0	{ 15, 23, 27, 29, 30}	0
{ 3, 6, 12, 17, 24}	1	{ 7, 14, 19, 25, 28}	0
{ 5, 9, 10, 18, 20}	1	{ 11, 13, 21, 22, 26}	1

Table 16-d.
F_2⁶, t⁶+t+1=0, g=t³+1
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4, 8, 16, 32}	0	{ 31, 47, 55, 59, 61, 62}	1
{ 3, 6, 12, 24, 33, 48}	0	{ 15, 30, 39, 51, 57, 60}	1
{ 5, 10, 17, 20, 34, 40}	1	{ 23, 29, 43, 46, 53, 58}	1
{ 7, 14, 28, 35, 49, 56}	0	{ 7, 14, 28, 35, 49, 56}	0
{ 11, 22, 25, 37, 44, 50}	1	{ 13, 19, 26, 38, 41, 52}	0

Table 16-e.
F_2⁷, t⁷+t+1=0, g=t²
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4, 8, 16, 32, 64}	0	{ 63, 95, 111, 119, 123, 125, 126}	1
{ 3, 6, 12, 24, 48, 65, 96}	0	{ 31, 62, 79, 103, 115, 121, 124}	1
{ 5, 10, 20, 33, 40, 66, 80}	0	{ 47, 61, 87, 94, 107, 117, 122}	1
{ 7, 14, 28, 56, 67, 97, 112}	1	{ 15, 30, 60, 71, 99, 113, 120}	0
{ 9, 17, 18, 34, 36, 68, 72}	0	{ 55, 59, 91, 93, 109, 110, 118}	0
{ 11, 22, 44, 49, 69, 88, 98}	0	{ 29, 39, 58, 78, 83, 105, 116}	0
{ 13, 26, 35, 52, 70, 81, 104}	1	{ 23, 46, 57, 75, 92, 101, 114}	0
{ 19, 25, 38, 50, 73, 76, 100}	1	{ 27, 51, 54, 77, 89, 102, 108}	1
{ 21, 37, 41, 42, 74, 82, 84}	1	{ 43, 45, 53, 85, 86, 90, 106}	1

Table 16-f.
F_2⁸, t⁸+t⁴+t³+t+1=0, g=t²+1
x	Tr(x)	x^-1	Tr(x^-1)
{ 1, 2, 4, 8, 16, 32, 64, 128}	0	{127, 191, 223, 239, 247, 251, 253, 254}	0
{ 3, 6, 12, 24, 48, 96, 129, 192}	0	{ 63, 126, 159, 207, 231, 243, 249, 252}	1
{ 5, 10, 20, 40, 65, 80, 130, 160}	1	{ 95, 125, 175, 190, 215, 235, 245, 250}	1
{ 7, 14, 28, 56, 112, 131, 193, 224}	0	{ 31, 62, 124, 143, 199, 227, 241, 248}	0
{ 9, 18, 33, 36, 66, 72, 132, 144}	1	{111, 123, 183, 189, 219, 222, 237, 246}	0
{ 11, 22, 44, 88, 97, 133, 176, 194}	1	{ 61, 79, 122, 158, 167, 211, 233, 244}	1
{ 13, 26, 52, 67, 104, 134, 161, 208}	0	{ 47, 94, 121, 151, 188, 203, 229, 242}	1
{ 15, 30, 60, 120, 135, 195, 225, 240}	1	{ 15, 30, 60, 120, 135, 195, 225, 240}	1
{ 19, 38, 49, 76, 98, 137, 152, 196}	0	{ 59, 103, 118, 157, 179, 206, 217, 236}	0
{ 21, 42, 69, 81, 84, 138, 162, 168}	1	{ 87, 93, 117, 171, 174, 186, 213, 234}	1
{ 23, 46, 92, 113, 139, 184, 197, 226}	0	{ 29, 58, 71, 116, 142, 163, 209, 232}	1
{ 25, 35, 50, 70, 100, 140, 145, 200}	0	{ 55, 110, 115, 155, 185, 205, 220, 230}	1
{ 27, 54, 99, 108, 141, 177, 198, 216}	0	{ 39, 57, 78, 114, 147, 156, 201, 228}	1
{ 37, 41, 73, 74, 82, 146, 148, 164}	0	{ 91, 107, 109, 173, 181, 182, 214, 218}	1
{ 43, 86, 89, 101, 149, 172, 178, 202}	1	{ 53, 77, 83, 106, 154, 166, 169, 212}	1
{ 45, 75, 90, 105, 150, 165, 180, 210}	0	{ 45, 75, 90, 105, 150, 165, 180, 210}	0

Lets answer the question: how many 1's are in each table?

Proposition 1: If m is odd prime then there is no Frobenius equivalence class that is it's own inverse.

Proof:

Let g be a generator of GF(2^m)^*. Let gⁿ be representative of it's Frobenius equivalence class. If the inverse of gⁿ is an element of the same Frobenius equivalence class then there exists a positive k such that (gⁿ)^{(2^k)} = g^{(n 2^k)} = g^-n, and thus n 2^k = -n [mod 2^m - 1], and thus n (2^k + 1) = 0 [mod 2^m - 1]. That implies that (2^k + 1) devides (2^m - 1), but for m odd prime this has no solutions because 2^m - 1 has the form cm + 1, where c is an integer, and m does not devide 2^k. $\qed$

Moreover, every element is part of a Frobenius equivalence class with size m and therefore every element is shown precisely once. The total number of elements in the table is q - 2, where the 2 takes the elements 0 and 1 into account that are not shown. Exactly half of all field elements (q/2) have trace 1. The trace of 0 is always 0 and the trace of 1 is 0 for odd m. Therefore, if m is an odd prime, the number of elements in the table for which the trace is 1 is equal to q/2 - 1, where the 1 takes the trace of element 1 into account, and if m is 2 then the number of elements in the table for which the trace is 1 is equal to q/2 = 2 (namely t and t + 1).

The number of 1's in the tables shown is 1/m times that, because we only show Frobenius equivalence classes with m elements at a time. Therefore, the number of 1's in the table with m = 2 is 1, and for m odd prime it is (q/2 - 1)/m.

If m is not prime then it's a bit harder.

Proposition 2: There are no elements in the tables whose inverse is in the same Frobenius equivalence class if m is odd.

Proof:

Let g be a generator of GF(2^m)^*. Let gⁿ be representative of a Frobenius equivalence class given in the table, then the smallest integer i > 0 such that (gⁿ)^(2ⁱ) = gⁿ is i = m. If the inverse of gⁿ is an element of the same Frobenius equivalence class then there exists a positive k such that (gⁿ)^{(2^k)} = g^-n. From that follows that squaring k times again, we get gⁿ back: (gⁿ)^{(2^2k)} = ((gⁿ)^{(2^k)})^{(2^k)} = (g^-n)^{(2^k)} = g^-(-n) = gⁿ. From that follows that 2k = m, because there is no value smaller than m for which this equality holds. Therefore, if m is odd, there are no elements with a Frobenius equivalence class size of m whose inverse is in the same Frobenius equivalence class. $\qed$

Let ect1(m) be the number of elements in Frobenius equivalence classes size m and trace 1. Then the ect1(m) can be calculated by taking the total number of elements with trace 1 and subtracting the number of elements with trace 1 that are in a Frobenius equivalence class with less than m elements. Those elements are precisely the m/d $\cdot$ w(m, d) elements with a proper divisor d of m. As seen before, the elements represented by even d have all trace 0, thus we only need to subtract the number of elements with a trace of 1 in the Frobenius equivalence class groups formed by the m/d $\cdot$ w(m, d) elements with odd d.

Proposition 3: The total number of elements with trace 1 in Frobenius equivalence classes with size m/d is independent of the chosen generator and is, for odd d, equal to the total number of elements with trace 1 in the Frobenius equivalence classes of w(m/d, 1), which is defined as ect1(m/d).

Proof:

Both, the definition of Frobenius equivalence class as well as trace are independent of the chosen basis. Consider a normal basis { b, b², b⁴, b⁸, ..., b^{2^m-1} }, then squaring means rotation of the binary vector that represents the element and therefore, if we need to square no less than m times before we get the original element back, one of the elements of the Frobenius equivalence class is a binary Lyndon word (which is the minimal element in the lexicographical ordering of all its rotations. The minimality implies that a Lyndon word is aperiodic, so differs from any of its non-trivial rotations). Note that there is a 1-on-1 correspondence between binary Lyndon words of size n and Frobenius equivalence classes of size n. Let the number of binary Lyndon words of size n with trace 1 be blwt1(n), it could be represented, for example, by the Lyndon word (abcde...) with n bits, then, because of the 1-on-1 correspondence blwt1(n) = ect1(n) / n.

Note that the trace of an element is equal to the sum of the trace of all it's basis elements. Since the trace of an element of a normal basis is 1, as was explained before, we see that the trace of an arbitrary element is the sum of the bits of its binary vector representation (modulo 2), or equivalently the sum of the bits of the binary Lyndon word corresponding to it's Frobenius equivalence class.

An element from a Frobenius equivalence class with size m/d will repeat after squaring m/d times. Therefore, an element from a Frobenius equivalence class with size m/d can be represented with the binary vector (relative to a normal basis): (abcde...)(abcde...)(abcde...)... repeated d times. Note that the trace is 0 if d is even. For odd d this clearly shows that the number of elements with trace 1 of such form are equal to the number of elements with trace 1 in (abcde...). $\qed$

See also this link that lists sequence A000048 as the number of binary Lyndon words with trace 1 as function of it's size.

As a result, we can write ect1(m) as follows,

ect1(2)	=	q/2			=	2	=	2 $\cdot$ 1
ect1(3)	=	q/2 - 1			=	3	=	3 $\cdot$ 1
ect1(4)	=	q/2			=	8	=	4 $\cdot$ 2
ect1(5)	=	q/2 - 1			=	15	=	5 $\cdot$ 3
ect1(6)	=	q/2	-	ect1(6/3)	=	30	=	6 $\cdot$ 5
ect1(7)	=	q/2 - 1			=	63	=	7 $\cdot$ 9
ect1(8)	=	q/2			=	128	=	8 $\cdot$ 16
ect1(9)	=	q/2 - 1	-	ect1(9/3)	=	252	=	9 $\cdot$ 28
ect1(10)	=	q/2	-	ect1(10/5)	=	510	=	10 $\cdot$ 51
ect1(11)	=	q/2 - 1			=	1023	=	11 $\cdot$ 93
ect1(12)	=	q/2	-	ect1(12/3)	=	2040	=	12 $\cdot$ 170
ect1(13)	=	q/2 - 1			=	4095	=	13 $\cdot$ 315
ect1(14)	=	q/2	-	ect1(14/7)	=	8190	=	14 $\cdot$ 585
ect1(15)	=	q/2 - 1	-	ect1(15/3) - ect1(15/5)	=	16365	=	15 $\cdot$ 1091
ect1(16)	=	q/2			=	32768	=	16 $\cdot$ 2048
ect1(17)	=	q/2 - 1			=	65535	=	17 $\cdot$ 65535
ect1(18)	=	q/2	-	ect1(18/3) - ect1(18/9)	=	131040	=	18 $\cdot$ 7280
ect1(19)	=	q/2 - 1			=	262143	=	19 $\cdot$ 13797
ect1(20)	=	q/2	-	ect1(20/5)	=	524280	=	20 $\cdot$ 26214
ect1(21)	=	q/2 - 1	-	ect1(21/3) - ect1(21/7)	=	1048509	=	21 $\cdot$ 49929
ect1(22)	=	q/2	-	ect1(22/11)	=	2097150	=	22 $\cdot$ 95325
ect1(23)	=	q/2 - 1			=	4194303	=	23 $\cdot$ 182361
ect1(24)	=	q/2	-	ect1(24/3)	=	8388480	=	24 $\cdot$ 349520
ect1(25)	=	q/2 - 1	-	ect1(25/5)	=	16777200	=	25 $\cdot$ 671088
ect1(26)	=	q/2	-	ect1(26/13)	=	33554430	=	26 $\cdot$ 1290555
ect1(27)	=	q/2 - 1	-	ect1(27/3) - ect1(27/9)	=	67108608	=	27 $\cdot$ 2485504

If we define ect1(1) = 1, then this can be written as:

$ect1(m) = 2^{m-1} - \sum_{\mathrm{odd}\text{ }d\text{, }d|m}{ect1(m/d)}$

This still doesn't give us the number of 1's in the tables: some elements are given twice, namely those whose inverse is in the same Frobenius equivalence class. As we saw before, this number is zero for odd m.

Before we continue, let us first have a closer look at field extensions. As was shown before, all fields have pⁿ elements, where p is a prime and n the degree of the field. So, if some larger field L is an extension of a smaller field K (meaning that K is a subfield of L) then both necessarily need to have the same characteristic p. Let the larger field have p^m elements, and the smaller field pⁿ elements, then n must devide m.

This is easy to understand by realizing that L is in fact K[s]/u(s)K[s], where s is the root of some irreducible polynomial u(s) over K of degree m/n. For example, let K have 2⁶ elements, thus it is isomorphic with F₆₄, or more specifically K = F₂[t]/(t⁶+t+1)F₂[t], where t⁶+t+1 is irreducible over F₂. [ Often this is written more concise as K = F₂[t]/<t⁶+t+1>, compare the longer notation with Z/nZ. More in general, R/I (pronounce: R over I); where R is a ring and I is called an Ideal of R. An Ideal has the property that if i $\in$ I then ri $\in$ I for any r $\in$ R. ] Now extent this field by adding an indeterminate s and then making it algebraically closed again: L = K[s]/u(s)K[s], where u(s) is irreducible over K. For example, let u(s) = s² + (t⁵ + t²)s + 1, which is irreducible over K. We can see both fields as a vector space over some basis. In the case of K we can choose the familiar basis { 1, t, t², t³, t⁴, t⁵ }, and represent every element as a binary vector consisting of the coefficients relative to this basis. Likewise, we can choose the basis { 1, s } for L, and write each element of L as a two dimensional vector with elements from K as coefficients. The total number of elements in L is therefore L = K² = 64² = 4096 = 2¹². But wait-a-minute! Aren't all fields with a given number of elements isomorphic? How can this L be isomorphic with the field that we've been working with all along: F₂[x]/<x¹²+x³+1>? And how does the mapping work that links elements of L to K in that case?

Ok, this mapping is a linear map: it preserves the algebraic relationships between elements. It is a so called homomorphism that assigns 1-on-1 (injective) an element in L to every element in K: $\alpha : K \rightarrow L$ , with the properties $\alpha$ (a + b) = $\alpha$ (a) + $\alpha$ (b), $\alpha$ (ab) = $\alpha$ (a) $\alpha$ (b) and $\alpha$ (1) = 1 for every a and b in K. [ Note that field homomorphisms are always injective, because its kernel (that what maps to 0) is a proper ideal (it doesn't contain 1, since $\alpha$ (1_K) = 1_L), which must therefore be zero because the only Ideal of a field F is (0) or the whole field itself: let I be a non-zero ideal of F. If a is a non-zero element of I then a^-1a = 1 is element of I and thus I = F. Moreover, if $\alpha$ (a) = $\alpha$ (b) then $\alpha$ (a-b) = 0 which, because the ideal is (0), implies that a - b = 0, and thus $\alpha$ is injective.] Let every element in L be represented by a 2-dimensional vector (k₁, k₂) where k₁ and k₂ are elements of (a field isomorphic with) K and the element is actually k₁ + k₂ $\cdot$ s. In this case it is trivial which elements in L correspond to those in K. Let k $\in$ K, then $\alpha$ (k) corresponds to the vector space spanned by the vector (1, 0).

Finding this correspondence between K = F₂[t]/<t⁶+t+1> and L = F₂[x]/<x¹²+x³+1> requires a little bit more work. First, we have to find an element in L (which we can very well call t) that satisfies the equation t⁶+t+1 = 0. If g is a generator of the multiplicative group L^* (L without it's zero), then it turns out that t = g⁶⁵, where 65 comes from L^* / K^* = 4095 / 63 = 65. The other roots of t⁶+t+1 = 0 can be found by applying Frobenius repeatedly to g⁶⁵, each of which could have been used for t as well, of course. Since t is a generator of K, g^65 can subsequently be used to find all elements in L that form the subgroup isomorphic with K in L.

Finally, to really see the link, lets express s in x too! Lets use g = x⁹ + x⁸ + x⁷ + x⁴ + x² + x as generator of L (as found by the function generator(void) in point/bspacetables3.cc). t = g⁶⁵ = x¹¹ + x¹⁰ + x⁸ + x⁷ + x + 1. Furthermore we have u(s) = s² + (t⁵ + t²)s + 1 = 0 $\longrightarrow$ s² + (x¹⁰ + x⁷ + x⁶ + x³ + x)s + 1 = 0 $\longrightarrow$ s = x¹¹ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + 1 or s = x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁵ + x³ + x + 1. And indeed, using one of those s, k₁ + k₂s, where k₁ and k₂ run from 0 to x⁵ + x⁴ + x³ + x² + x + 1 generates exactly all elements in L from 0 to x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1! So, K[s]/<s²+(t⁵+t²)s+1> and F₂[x]/<x¹²+x³+1> are the same thing after all!

Proposition 4: The elements of a Frobenius equivalence class size m over F_2^m are not in a proper subfield of the field.

Proof:

Let L = F_2^m be an extension of the proper subfield K = F_2ⁿ. This means that n < m and n|m. Let x $\in$ L be such that the smallest integer k such that x^{2^k} = x is for k = m, in other words x is in an Frobenius equivalence class size m over F_2^m. If x $\in$ K then the minimal polynomial of x has a degree d <= n < m, and the roots of that polynomial can be found by applying Frobenius d times. In other words, x^{2^d} = x and we have a contradiction. $\qed$

Now we're ready to prove the following proposition.

Proposition 5: The number of Frobenius equivalence classes size m that are their own inverse and where m is even, is blwt1(m/2).

Proof:

blwt1(m/2) is the number of Lyndon words with length m/2 and trace 1. This sequence is well-known, and for example given by A000048. Thus, blwt1(1) = 1, and we can experimentally verify that the proposition holds for m = 2, therefore, for the remainder of the proof, with m = 2n, assume n > 1.

We already saw that a Lyndon word length m has a one-on-one correspondence to the number of Frobenius equivalence classes of size m. Therefore, the proposition is equivalent with: The number of Frobenius equivalence classes size 2n over F_2²ⁿ that are their own inverse is equal to the number of Frobenius equivalence classes size n over F_2ⁿ, with n > 0 (although we only need to prove it for n > 1).

In terms of elements, since the number of elements in a Frobenius equivalence class is equal to its size, we still have to prove: For n > 1, the number of elements in F_2²ⁿ that are not in a proper subfield of F_2²ⁿ and that have an inverse that is also not in a proper subfield of F_2²ⁿ, is equal to twice the number of elements in F_2ⁿ that are not in a proper subfield of F_2ⁿ and have trace 1.

Let x $\in$ F_2ⁿ and y $\in$ F_2²ⁿ. Consider the equation y² + xy + 1 = 0. This being a quadratic equation with coeficients from F_2ⁿ, there are three possibilities: 1) The equation has one solution, 2) The equation has no solution over F_2ⁿ, 3) The equation has two solutions over F_2ⁿ. Case 1) is not interesting because this only happens when x = 0 (namely, the two solutions are y and y + x) and 0 cannot be represented by a Lyndon word for n > 1. Two solutions over F_2²ⁿ always exist: y and 1/y, after all y $\ne$ 0 and (1/y)² + x/y + 1 = (1 + xy + y²)/y² = 0. In order for y not to be in a proper subgroup of F_2²ⁿ, the equation may not have solutions over F_2ⁿ (otherwise y would be in the proper subgroup F_2ⁿ). Moreover, x may not be in a proper subgroup J of K = F_2ⁿ (so that [K:J] > 1), because if it were then y would be in a subgroup S such that [S:F₂] = [S:J][J:F₂] = 2[J:F₂] < [L:F₂] = [L:K][K:J][J:F₂] = 2[K:J][J:F₂] and therefore in a proper subgroup of L. Therefore, since both are roots of the same irreducible polynomial (case 2), they are in the same Frobenius equivalence class (namely, y^{2^k} = 1/y, as we saw before, with k = n = m/2). Knowing that y + 1/y = x, and since 1/y = y^2ⁿ, we can write y + y^2ⁿ = x, and thus see that there will only be solutions over F_2ⁿ if Tr(x) = 0. We demand case 2, no solutions, and thus Tr(x) = 1. As such we see that the pair of solutions (y, 1/y) over F_2²ⁿ are not in a proper subgroup of F_2²ⁿ if and only if x is not in a proper subgroup of F_2ⁿ and Tr(x) = 1. Finally we should probably prove that for different x, the solutions y are different, but I consider that trivial, as well as that every y is the solution of the quadratic for some value of x, but that follows trivially from the fact that L is a field extension of K. $\qed$

The program testsuite/point/bspacetables3.cc was used to count the number of Frobenius equivalence classes with size m, either any, with trace 1, being it's own inverse or both. Also the number of generators and normal basis were counted with and without trace 1, and a combination thereof. Finally the number of Frobenius equivalence classes with a trace equal to the trace of it's inverse (solutions accounted for by w(m, 1)) were counted, as well as those with extra demands like trace 1, generator, normal base and combinations thereof.

Detailed results can be found on the page Brute force counting data for b = 1. A summary follows below.

Summary

Code	Description	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
A	Number of Frobenius equivalence classes (foc(m) / m = A001037):	1	2	3	6	9	18	30	56	99	186	335	630	1161	2182	4080	7710	14532	27594	52377	99858	190557	364722	698870	1342176	2580795	4971008	9586395	18512790	35790267	69273666
B	Number of Frobenius equivalence classes with trace 1 (blwt1(m) = A000048 (see also proposition 3)):	1	1	2	3	5	9	16	28	51	93	170	315	585	1091	2048	3855	7280	13797	26214	49929	95325	182361	349520	671088	1290555	2485504	4793490	9256395	17895679	34636833
C	Number of Frobenius equivalence classes that are their own inverse (blwt1(m/2) (propositions 2 and 5)):	1	0	1	0	1	0	2	0	3	0	5	0	9	0	16	0	28	0	51	0	93	0	170	0	315	0	585	0	1091	0
D	Number of Frobenius equivalence classes that are their own inverse with trace 1 (depends on w(m/2, 1)*):	1	0	1	0	0	0	1	0	2	0	2	0	4	0	9	0	14	0	24	0	48	0	86	0	154	0	294	0	550	0
E	Number of generators (euler_phi(2^m - 1) / m = A011260):	1	2	2	6	6	18	16	48	60	176	144	630	756	1800	2048	7710	7776	27594	24000	84672	120032	356960	276480	1296000	1719900	4202496	4741632	18407808	17820000	69273666
F	Number of generators with trace 1 (no formula):	1	1	1	3	4	9	7	25	31	87	72	315	381	901	1017	3855	3890	13797	12000	42344	60043	178431	138224	648031	860059	2101353	2370715	9203747	8908940	34636833
G	Number of normal basis (num_normal(m) = A027362):	1	1	2	3	4	7	16	21	48	93	128	315	448	675	2048	3825	5376	13797	24576	27783	95232	182183	262144	629145	1290240	1835001	3670016	9256395	11059200	28629151
H	Number of normal basis that exist of generators (no formula, A107222):	1	1	1	3	3	7	7	19	29	87	52	315	291	562	1017	3825	2870	13797	11255	23579	59986	178259	103680	607522	859849	1551227	1815045	9203747	5505966	28629151
I	Number of solutions, w(m, 1) (this is what we want to know) (A137503):	1	0	1	4	3	8	16	28	45	96	167	308	579	1100	2018	3852	7280	13776	26133	49996	95223	182248	349474	671176	1289925	2485644	4793355	9255700	17894421	34638296
J	Number of solutions with trace 1 (no formula):	1	0	1	2	2	4	9	14	24	48	86	154	294	550	1017	1926	3654	6888	13092	24998	47658	91124	174822	335588	645120	1242822	2396970	4627850	8947756	17319148
K	Number of solutions that are generators (no formula):	1	0	0	4	2	8	10	26	26	94	76	308	378	902	1014	3852	3908	13776	11944	42460	60014	178414	138360	648042	859642	2101290	2370858	9202954	8910288	34638296
L	Number of solutions that are generators with trace 1 (no formula):	1	0	0	2	2	4	4	14	14	46	38	154	192	452	500	1926	1956	6888	5972	21238	30034	89158	69164	324052	429930	1050750	1185328	4601320	4454084	17319148
M	Number of solutions that are normal basis (no formula):	1	0	1	2	2	4	9	12	22	48	62	154	224	332	1017	1912	2712	6888	12286	13912	47610	91028	131094	314584	644966	917600	1835144	4627850	5529896	14314976
N	Number of solutions that are normal basis and generators (no formula):	1	0	0	2	2	4	4	12	13	46	25	154	145	277	500	1912	1459	6888	5603	11876	30005	89062	51888	303761	429829	775566	907684	4601320	2753361	14314976

* Conjecture: the number of Frobenius equivalence classes that are their own inverse with trace 1 is zero if m is odd (proposition 2), equal to w(m/2, 1)/2 if m/2 is odd, or equal to (w(m/2, 1) + et1c(m/4)/(m/4))/2 is m/2 is even.

Ok, anti-climax ... I found how to generate w(m,1), as is now also shown Neil Sloane's integer sequence database as entry A137503.

The following program generates directly the #E (table 1):

#include <iostream>
#include <iomanip>

// The number of elements x that have an inverse 1/x (which is every x except 0) that satisfy Tr(x) = Tr(1/x).
unsigned long s(int m)
{
  static unsigned long cache[64];
  if (cache[m])
    return cache[m];

  if (m == 1)
    return 1;
  if (m == 2)
    return 3;
  unsigned long result = (1UL << m) - 1;
  result -= 1 + s(m - 1) + 2 * s(m - 2);

  cache[m] = result;
  return result;
}

int main()
{
  for (int m = 1; m < 64; ++m)
    std::cout << std::setw(2) << m << ": " << std::setw(14) << (2 * s(m) + 2) << '\n';
}

Table 1.
m	#E
1	4
2	8
3	4
4	16
5	44
6	56
7	116
8	288
9	508
10	968
11	2116
12	4144
13	8012
14	16472
15	33044
16	65088
17	130972
18	263144
19	523492
20	1047376
21	2099948
22	4193912
23	8383412
24	16783200
25	33558844
26	67092488
27	134225284
28	268460656
29	536830604
30	1073731736
31	2147574356
32	4294896768
33	8589823708
34	17180121128
35	34359708196
36	68719003024
37	137439487532
38	274878320312
39	549754332404
40	1099512282528
41	2199025563772
42	4398042893384
43	8796092023492
44	17592194278576
45	35184365852108
46	70368733946072
47	140737511060372
48	281474974468800
49	562949910253084
50	1125899954494568
51	2251799852369764
52	4503599493382096
53	9007199311360364
54	18014398720839416
55	36028796694367796
56	72057593939809248
57	144115188823166908
58	288230375600638088
59	576460751359875076
60	1152921506652542704
61	2305843009055095052
62	4611686014494595352
63	9223372041104766164

Of course, much more analysis will follow...

Cracking parameter b of the elliptic curve

Summary