Main Page   Reference Manual   Compound List   File List  

Cracking parameter b of the elliptic curve

Today, 24 November 2004, I found the answer to the question why #E0 + #E1 = 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: x3 + ax2 + b = y2 + 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 x2, we see that there will be a solution for a non-zero value of x when x + a + b/x2 = (y/x)2 + y/x.  And because of theorem 5, this only has a solution when Tr(x + a + b/x2) = 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 #E0 = 2 + 2 $\kappa_0$ and #E1 = 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 #E0 + #E1 = 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/x2). 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 #E0 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: y2 + xy = x3 + 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
28
34
416
544
656
7116
8288
9508
10968
112116
124144
138012
1416472
1533044
1665088
17130972
18263144
19523492
201047376
212099948
224193912
238383412
2416783200
2533558844
2667092488
27134225284
28268460656
29536830604
301073731736
312147574356

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
23
31
47
521
627
757
8143
9253
10483
111057
122071
134005
148235
1516521
1632543
1765485
18131571
19261745
20523687
211049973
222096955
234191705
248391599
2516779421
2633546243
2767112641
28134230327
29268415301
30536865867
311073787177

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
221
300
46
5204
626
7568
8142
9252
10482
11105696
122070
134004308
148234
1516520
1632542
17654843852
18131570
1926174413776
20523686
211049972
222096954
234191704182248
248391598
2516779420
2633546242
2767112640
28134230326
292684153009255700
30536865866
31107378717634638296

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 x2n = 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 - 1w(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)
221
300
4611
5204
626321
7568
81421631
9252280
104824561
11105696
1220701679121
134004308
148234579181
1516520110040
163254220183031
17654843852
18131570728056321
1926174413776
205236862613399611
2110499724999680
222096954952231861
234191704182248
248391598349474335169321
25167794206711764
263354624212899256301
27671126402485644280
28134230326479335511611811
292684153009255700
30536865866178944212182453621
31107378717634638296

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 = (213 - 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 x2n = 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 2m - 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 (x4 = 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 x2 = 1/x (recall that Tr(x) = Tr(x2) 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.
F22, t2+t+1=0
x1/xx2x2+x+1
000
t0=1 t0=1 11
t1=t t2=t + 1 t + 10
t2=t + 1 t1=t t0

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 x2 + 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.
F24, t4+t+1=0, g=t
x1/xx2x2+x+1
g0=1 g0=1 11
g1=g g14=g3 + 1 g2g2 + g + 1
g2=g2 g13=g3 + g2 + 1 g + 1g2 + g
g3=g3 g12=g3 + g2 + g + 1 g3 + g2g2 + 1
g4=g+1 g11=g3 + g2 + g g2 + 1g2 + g + 1
g5=g2 + g g10=g2 + g + 1 g2 + g + 10
g6=g3 + g2 g9=g3 + g g3 + g2 + g + 1g
g7=g3 + g + 1 g8=g2 + 1 g3 + 1g + 1
g8=g2 + 1 g7=g3 + g + 1 gg2 + g
g9=g3 + g g6=g3 + g2 g3g + 1
g10=g2 + g + 1 g5=g2 + g g2 + g0
g11=g3 + g2 + g g4=g+1 g3 + g + 1g2
g12=g3 + g2 + g + 1 g3=g3 g3 + gg2
g13=g3 + g2 + 1 g2=g2 g3 + g2 + gg
g14=g3 + 1 g1=g g3 + g2 + 1g2 + 1

Here I used the same color for elements in the same Frobenius equivalence class. For example, g6 and g9 are in the same Frobenius equivalence class because ((g6)2)2 = s24 = g9 (recall that g2m = g and thus g15 = 1).

Note that the two values (g5 and g10) together with g0 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.
Z3
n2n
00
12
21

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 (pn - 1) divides (pm - 1), giving a subgroup under multiplication with size (pm - 1) / (pn - 1) = pm/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.
F26, t6+t+1=0
x = gnGCD(n, 63)1/xTr(x)Tr(1/x)dx2+x+1x3+x+1
g1=t1g62=t5+1011t2+t+1t3+t+1
g2=t21g61=t5+t4+1011t4+t2+1t2+t
g3=t33g60=t5+t4+t3+1011t3+tt4+1
g4=t41g59=t5+t4+t3+t2+1011t4+t3+t2+1t4+t2
g5=t51g58=t5+t4+t3+t2+t+1111t4+1t3+1
g6=t+13g57=t5+t4+t3+t2+t011t2+t+1t3+t2+1
g7=t2+t7g56=t4+t3+t2+t+1001t4+t+1t5+t4+t3+t2
g8=t3+t21g55=t5+t3+t2+t011t4+t3+t2+tt4+t3+t2
g9=t4+t39g54=t4+t2+t+1002t4+t2+tt4+t2+t+1
g10=t5+t41g53=t5+t3+t111t3+t2+1t
g11=t5+t+11g52=t4+t2+1101t4+t2+t+1t5+t4
g12=t2+13g51=t5+t3+t+1011t4+t2+1t4+t
g13=t3+t1g50=t5+t4+t2011t3+t2t5+t4+t3+t2+1
g14=t4+t27g49=t4+t3+t001t3+1t5+t3+t2+t+1
g15=t5+t33g48=t3+t2+1101t4+t3+tt5+t4
g16=t4+t+11g47=t5+t2+t+1011t4+t3+t+1t4+t3+t2+t+1
g17=t5+t2+t1g46=t5+t4+t111t+1t3+t2
g18=t3+t2+t+19g45=t4+t3+1002t4+t3t4+t3+1
g19=t4+t3+t2+t1g44=t5+t3+t2+1011t2t5+1
g20=t5+t4+t3+t21g43=t5+t4+t2+t+1111t4+tt2
g21=t5+t4+t3+t+121g42=t5+t4+t3+t1130t5+t4+t3+t+1
g22=t5+t4+t2+11g41=t4+t3+t2+1101t4+t3+1t5+t4+t3+t2
g23=t5+t3+11g40=t5+t3+t2+t+1111t4+t3+tt5+t3+t+1
g24=t4+13g39=t5+t4+t2+t011t4+t3+t2+1t3
g25=t5+t1g38=t4+t3+t+1101t4+t2+t+1t5+t2+t
g26=t2+t+11g37=t5+t3+t2011t4+t+1t5+t3+t2+t
g27=t3+t2+t9g36=t4+t2+t002t4+t30
g28=t4+t3+t27g35=t3+t+1001tt5+t2+t
g29=t5+t4+t31g34=t5+t2111t2+tt5+t3
g30=t5+t4+t+13g33=t4+t101t3+t+1t5+t4+t3+t2
g31=t5+t2+11g32=t3+1101t2+1t4+t2+t+1
g32=t3+11g31=t5+t2+1011t3+tt4+t3+t
g33=t4+t3g30=t5+t4+t+1011t4+t3+t+1t2+1
g34=t5+t21g29=t5+t4+t3111t2+1t4+t+1
g35=t3+t+17g28=t4+t3+t2001t3+t2t5+t4
g36=t4+t2+t9g27=t3+t2+t002t3+t2+t+1t3+t2+t
g37=t5+t3+t21g26=t2+t+1101t3+t2+tt5
g38=t4+t3+t+11g25=t5+t011t4t5+t4+1
g39=t5+t4+t2+t3g24=t4+1101t4+t3+t2+t+1t5
g40=t5+t3+t2+t+11g23=t5+t3+1111t3t4
g41=t4+t3+t2+11g22=t5+t4+t2+1011tt5+t2+1
g42=t5+t4+t3+t21g21=t5+t4+t3+t+11130t5+t4+t3+t
g43=t5+t4+t2+t+11g20=t5+t4+t3+t2111t4+t3+t2+t+1t5+t4+t3+t2+t
g44=t5+t3+t2+11g19=t4+t3+t2+t101t3+t2+tt5+t3+t2+t+1
g45=t4+t3+19g18=t3+t2+t+1002t4+t2+t0
g46=t5+t4+t1g17=t5+t2+t111t3+t+1t5+t4+t2+t
g47=t5+t2+t+11g16=t4+t+1101t+1t3+t2+t
g48=t3+t2+13g15=t5+t3011t4+t3+t2+tt+1
g49=t4+t3+t7g14=t4+t2001t4t5
g50=t5+t4+t21g13=t3+t101t4+t3+1t5+t2
g51=t5+t3+t+13g12=t2+1101t4+t3+t2t5+t2
g52=t4+t2+11g11=t5+t+1011t3+1t5+t2+t+1
g53=t5+t3+t1g10=t5+t4111t4+t3+t2t5+t4+t3+1
g54=t4+t2+t+19g9=t4+t3002t3+t2+t+10
g55=t5+t3+t2+t1g8=t3+t2101t3t4+t3+1
g56=t4+t3+t2+t+17g7=t2+t001t2t5+t2
g57=t5+t4+t3+t2+t3g6=t+1101t4+t2t5+t2+t
g58=t5+t4+t3+t2+t+11g5=t5111t4+t2t5+t4+t+1
g59=t5+t4+t3+t2+11g4=t4101t4+tt4+t2+t+1
g60=t5+t4+t3+13g3=t3101t2+tt5+t3+t2+t+1
g61=t5+t4+11g2=t2101t3+t2+1t3+t2+t
g62=t5+11g1=t101t4+1t4+t3+1

Here we see again the two elements that give rise to the w(6,3) as g21 and g42. Together with 1 they form the multiplicative subgroup GF(22)* as can be seen from the fact that x2+x+1 in the second column from the right is zero. Likewise, the third column contains zeroes for the roots of x3+x+1: g27, g45 and g54 which are thus, elements of the multiplicative group GF(23)*. The remaining elements of that group, besides the multiplicative unity, are g9, g18 and g36. 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(23)* is isomorphic with $\mathbb{Z}_7$:

Table 9.
Z7
n6n
00
16
25
34
43
52
61

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

Looking at F26 again, we only see one other (besides { g21, g42 }}) Frobenius equivalence class that automatically adds to the count of solutions in the form of the elements { t7, t14, t28, t35, t49, t56 }, 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={2i}, 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 2k + 1 = 0 (mod n), then let k be the least positive such, then S = { 20, 21, ..., 2(2k-1)} since 22k = 1 (mod n), thus S = 2k is even, and 2i + 2k+i = 2i + (-1) $\cdot$ 2i = 0 (mod n), i.e. all elements are paired up. Let 2i = x in S then there exists a y in S such that x + y = 0 (mod n) thus 2i + 2k $\cdot$ 2i = 0 (mod n), thus 2k $\cdot$ 2i = (-1) $\cdot$ 2i (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 2k + 1 = 0 (mod n).

And indeed, 9 = 23 + 1, where the exponent k = 3 gives rise to 2k = 6 elements in the Frobenius equivalence class of w(m, m/6). Moreover, 3 = 21 + 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 2m - 1 has a factor n such that there exists a positive k such that 2k + 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 (2m - 1) / gcd(2m - 1, n) instead of gcd(2m - 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.
F26, t6+t+1=0
x = gn63/GCD(n, 63)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g9=t4+t37g54=t4+t2+t+1003t4+t2+tt4+t2+t+1
g18=t3+t2+t+17g45=t4+t3+1003t4+t3t4+t3+1
g21=t5+t4+t3+t+13g42=t5+t4+t3+t1120t5+t4+t3+t+1
g27=t3+t2+t7g36=t4+t2+t003t4+t30
g36=t4+t2+t7g27=t3+t2+t003t3+t2+t+1t3+t2+t
g42=t5+t4+t3+t3g21=t5+t4+t3+t+11120t5+t4+t3+t
g45=t4+t3+17g18=t3+t2+t+1003t4+t2+t0
g54=t4+t2+t+17g9=t4+t3003t3+t2+t+10
Table 10-b.
F212, t12+t3+1=0
x = gn4095/GCD(n, 4095)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g585=t10+t7+t5+t+17g3510=t11+t8+t7+t003t11+t8+t7+t+1t11+t8+t7+t
g1170=t11+t10+t8+t5+17g2925=t10+t7+t5+t003t10+t7+t5+t+1t10+t7+t5+t
g1365=t6+t33g2730=t6+t3+10020t6+t3
g1755=t11+t10+t8+t57g2340=t11+t8+t7+t+1003t10+t7+t5+t+10
g2340=t11+t8+t7+t+17g1755=t11+t10+t8+t5003t11+t10+t8+t5+1t11+t10+t8+t5
g2730=t6+t3+13g1365=t6+t30020t6+t3+1
g2925=t10+t7+t5+t7g1170=t11+t10+t8+t5+1003t11+t8+t7+t+10
g3510=t11+t8+t7+t7g585=t10+t7+t5+t+1003t11+t10+t8+t5+10
Table 10-c.
F218, t18+t3+1=0
x = gn262143/GCD(n, 262143)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g37449=t12+t6+t3+17g224694=t12+t9003t9+t6+t3+10
g74898=t12+t9+17g187245=t9+t6+t3+1003t12+t6+t30
g87381=t15+t12+t9+t3+13g174762=t15+t12+t9+t31120t15+t12+t9+t3+1
g112347=t12+t6+t37g149796=t9+t6+t3003t9+t6+t3+1t9+t6+t3
g149796=t9+t6+t37g112347=t12+t6+t3003t12+t90
g174762=t15+t12+t9+t33g87381=t15+t12+t9+t3+11120t15+t12+t9+t3
g187245=t9+t6+t3+17g74898=t12+t9+1003t12+t9t12+t9+1
g224694=t12+t97g37449=t12+t6+t3+1003t12+t6+t3t12+t6+t3+1
Table 10-d.
F224, t24+t4+t3+t+1=0
x = gn16777215/GCD(n, 16777215)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g2396745=t15+t14+t13+t9+t7+t5+t3+t2+17g14380470=t18+t15+t13+t8+t7+t6+t5003t18+t15+t13+t8+t7+t6+t5+1t18+t15+t13+t8+t7+t6+t5
g4793490=t18+t14+t9+t8+t6+t3+t2+17g11983725=t15+t14+t13+t9+t7+t5+t3+t2003t15+t14+t13+t9+t7+t5+t3+t2+1t15+t14+t13+t9+t7+t5+t3+t2
g5592405=t12+t6+t3+t2+t3g11184810=t12+t6+t3+t2+t+10020t12+t6+t3+t2+t
g7190235=t18+t14+t9+t8+t6+t3+t27g9586980=t18+t15+t13+t8+t7+t6+t5+1003t15+t14+t13+t9+t7+t5+t3+t2+10
g9586980=t18+t15+t13+t8+t7+t6+t5+17g7190235=t18+t14+t9+t8+t6+t3+t2003t18+t14+t9+t8+t6+t3+t2+1t18+t14+t9+t8+t6+t3+t2
g11184810=t12+t6+t3+t2+t+13g5592405=t12+t6+t3+t2+t0020t12+t6+t3+t2+t+1
g11983725=t15+t14+t13+t9+t7+t5+t3+t27g4793490=t18+t14+t9+t8+t6+t3+t2+1003t18+t15+t13+t8+t7+t6+t5+10
g14380470=t18+t15+t13+t8+t7+t6+t57g2396745=t15+t14+t13+t9+t7+t5+t3+t2+1003t18+t14+t9+t8+t6+t3+t2+10

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.
F23, t3+t+1=0
x = gn7/GCD(n, 7)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g1=t7g6=t2+1013t2+t+10
g2=t27g5=t2+t+1013t+10
g3=t+17g4=t2+t103t2+t+1t2+t
g4=t2+t7g3=t+1013t2+10
g5=t2+t+17g2=t2103t2+1t2
g6=t2+17g1=t103t+1t
Table 11-b.
F29, t9+t+1=0
x = gn511/GCD(n, 511)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g73=t8+t7+t6+t4+t+17g438=t8+t5+t3+t2+t103t8+t5+t3+t2+t+1t8+t5+t3+t2+t
g146=t7+t6+t5+t4+t3+t2+17g365=t8+t7+t6+t4+t103t8+t7+t6+t4+t+1t8+t7+t6+t4+t
g219=t7+t6+t5+t4+t3+t27g292=t8+t5+t3+t2+t+1013t8+t7+t6+t4+t+10
g292=t8+t5+t3+t2+t+17g219=t7+t6+t5+t4+t3+t2103t7+t6+t5+t4+t3+t2+1t7+t6+t5+t4+t3+t2
g365=t8+t7+t6+t4+t7g146=t7+t6+t5+t4+t3+t2+1013t8+t5+t3+t2+t+10
g438=t8+t5+t3+t2+t7g73=t8+t7+t6+t4+t+1013t7+t6+t5+t4+t3+t2+10
Table 11-c.
F215, t15+t+1=0
x = gn32767/GCD(n, 32767)1/xTr(x)Tr(1/x)m/dx2+x+1x3+x+1
g4681=t12+t10+t9+t5+t4+t7g28086=t9+t8+t6+t5+t4+t3+t2+1013t12+t10+t8+t6+t3+t2+t+10
g9362=t9+t8+t6+t5+t4+t3+t27g23405=t12+t10+t8+t6+t3+t2+t+1013t12+t10+t9+t5+t4+t+10
g14043=t12+t10+t9+t5+t4+t+17g18724=t12+t10+t8+t6+t3+t2+t103t12+t10+t8+t6+t3+t2+t+1t12+t10+t8+t6+t3+t2+t
g18724=t12+t10+t8+t6+t3+t2+t7g14043=t12+t10+t9+t5+t4+t+1013t9+t8+t6+t5+t4+t3+t2+10
g23405=t12+t10+t8+t6+t3+t2+t+17g9362=t9+t8+t6+t5+t4+t3+t2103t9+t8+t6+t5+t4+t3+t2+1t9+t8+t6+t5+t4+t3+t2
g28086=t9+t8+t6+t5+t4+t3+t2+17g4681=t12+t10+t9+t5+t4+t103t12+t10+t9+t5+t4+t+1t12+t10+t9+t5+t4+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 = gn such that (gn)2m/d = gn (= (gn)20), 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.
F23, t3+t+1=0
x = gn7/GCD(n, 7)1/xTr(x)Tr(1/x)m/d
g1=t7g6=t2+1013
g2=t27g5=t2+t+1013
g3=t+17g4=t2+t103
g4=t2+t7g3=t+1013
g5=t2+t+17g2=t2103
g6=t2+17g1=t103
Table 15-b.
F24, t4+t+1=0
x = gn15/GCD(n, 15)1/xTr(x)Tr(1/x)m/d
g1=t15g14=t3+1014
g2=t215g13=t3+t2+1014
g3=t35g12=t3+t2+t+1114
g4=t+115g11=t3+t2+t014
g6=t3+t25g9=t3+t114
g7=t3+t+115g8=t2+1104
g8=t2+115g7=t3+t+1014
g9=t3+t5g6=t3+t2114
g11=t3+t2+t15g4=t+1104
g12=t3+t2+t+15g3=t3114
g13=t3+t2+115g2=t2104
g14=t3+115g1=t104
Table 15-c.
F25, t5+t2+1=0
x = gn31/GCD(n, 31)1/xTr(x)Tr(1/x)m/d
g1=t31g30=t4+t005
g2=t231g29=t3+1005
g3=t331g28=t4+t2+t105
g4=t431g27=t3+t+1005
g5=t2+131g26=t4+t2+t+1115
g6=t3+t31g25=t4+t3+1105
g7=t4+t231g24=t4+t3+t2+t015
g8=t3+t2+131g23=t3+t2+t+1005
g9=t4+t3+t31g22=t4+t2+1115
g10=t4+131g21=t4+t3115
g11=t2+t+131g20=t3+t2115
g12=t3+t2+t31g19=t2+t105
g13=t4+t3+t231g18=t+1115
g14=t4+t3+t2+131g17=t4+t+1015
g15=t4+t3+t2+t+131g16=t4+t3+t+1005
g16=t4+t3+t+131g15=t4+t3+t2+t+1005
g17=t4+t+131g14=t4+t3+t2+1105
g18=t+131g13=t4+t3+t2115
g19=t2+t31g12=t3+t2+t015
g20=t3+t231g11=t2+t+1115
g21=t4+t331g10=t4+1115
g22=t4+t2+131g9=t4+t3+t115
g23=t3+t2+t+131g8=t3+t2+1005
g24=t4+t3+t2+t31g7=t4+t2105
g25=t4+t3+131g6=t3+t015
g26=t4+t2+t+131g5=t2+1115
g27=t3+t+131g4=t4005
g28=t4+t2+t31g3=t3015
g29=t3+131g2=t2005
g30=t4+t31g1=t005
Table 15-d.
F26, t6+t+1=0
x = gn63/GCD(n, 63)1/xTr(x)Tr(1/x)m/d
g1=t63g62=t5+1016
g2=t263g61=t5+t4+1016
g3=t321g60=t5+t4+t3+1016
g4=t463g59=t5+t4+t3+t2+1016
g5=t563g58=t5+t4+t3+t2+t+1116
g6=t+121g57=t5+t4+t3+t2+t016
g7=t2+t9g56=t4+t3+t2+t+1006
g8=t3+t263g55=t5+t3+t2+t016
g10=t5+t463g53=t5+t3+t116
g11=t5+t+163g52=t4+t2+1106
g12=t2+121g51=t5+t3+t+1016
g13=t3+t63g50=t5+t4+t2016
g14=t4+t29g49=t4+t3+t006
g15=t5+t321g48=t3+t2+1106
g16=t4+t+163g47=t5+t2+t+1016
g17=t5+t2+t63g46=t5+t4+t116
g19=t4+t3+t2+t63g44=t5+t3+t2+1016
g20=t5+t4+t3+t263g43=t5+t4+t2+t+1116
g22=t5+t4+t2+163g41=t4+t3+t2+1106
g23=t5+t3+163g40=t5+t3+t2+t+1116
g24=t4+121g39=t5+t4+t2+t016
g25=t5+t63g38=t4+t3+t+1106
g26=t2+t+163g37=t5+t3+t2016
g28=t4+t3+t29g35=t3+t+1006
g29=t5+t4+t363g34=t5+t2116
g30=t5+t4+t+121g33=t4+t106
g31=t5+t2+163g32=t3+1106
g32=t3+163g31=t5+t2+1016
g33=t4+t21g30=t5+t4+t+1016
g34=t5+t263g29=t5+t4+t3116
g35=t3+t+19g28=t4+t3+t2006
g37=t5+t3+t263g26=t2+t+1106
g38=t4+t3+t+163g25=t5+t016
g39=t5+t4+t2+t21g24=t4+1106
g40=t5+t3+t2+t+163g23=t5+t3+1116
g41=t4+t3+t2+163g22=t5+t4+t2+1016
g43=t5+t4+t2+t+163g20=t5+t4+t3+t2116
g44=t5+t3+t2+163g19=t4+t3+t2+t106
g46=t5+t4+t63g17=t5+t2+t116
g47=t5+t2+t+163g16=t4+t+1106
g48=t3+t2+121g15=t5+t3016
g49=t4+t3+t9g14=t4+t2006
g50=t5+t4+t263g13=t3+t106
g51=t5+t3+t+121g12=t2+1106
g52=t4+t2+163g11=t5+t+1016
g53=t5+t3+t63g10=t5+t4116
g55=t5+t3+t2+t63g8=t3+t2106
g56=t4+t3+t2+t+19g7=t2+t006
g57=t5+t4+t3+t2+t21g6=t+1106
g58=t5+t4+t3+t2+t+163g5=t5116
g59=t5+t4+t3+t2+163g4=t4106
g60=t5+t4+t3+121g3=t3106
g61=t5+t4+163g2=t2106
g62=t5+163g1=t106

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, g2 and g4.

Table 16-a.
F23, t3+t+1=0, g=t2
xTr(x)x-1Tr(x-1)
{ 1, 2, 4}0{ 3, 5, 6}1
Table 16-b.
F24, t4+t+1=0, g=t
xTr(x)x-1Tr(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.
F25, t5+t2+1=0, g=t2
xTr(x)x-1Tr(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.
F26, t6+t+1=0, g=t3+1
xTr(x)x-1Tr(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.
F27, t7+t+1=0, g=t2
xTr(x)x-1Tr(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.
F28, t8+t4+t3+t+1=0, g=t2+1
xTr(x)x-1Tr(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(2m)*. Let gn be representative of it's Frobenius equivalence class. If the inverse of gn is an element of the same Frobenius equivalence class then there exists a positive k such that (gn)(2k) = g(n 2k) = g-n, and thus n 2k = -n [mod 2m - 1], and thus n (2k + 1) = 0 [mod 2m - 1]. That implies that (2k + 1) devides (2m - 1), but for m odd prime this has no solutions because 2m - 1 has the form cm + 1, where c is an integer, and m does not devide 2k. $\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(2m)*. Let gn be representative of a Frobenius equivalence class given in the table, then the smallest integer i > 0 such that (gn)(2i) = gn is i = m. If the inverse of gn is an element of the same Frobenius equivalence class then there exists a positive k such that (gn)(2k) = g-n. From that follows that squaring k times again, we get gn back: (gn)(22k) = ((gn)(2k))(2k) = (g-n)(2k) = g-(-n) = gn. 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, b2, b4, b8, ..., b2m-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 pn 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 pm elements, and the smaller field pn 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 26 elements, thus it is isomorphic with F64, or more specifically K = F2[t]/(t6+t+1)F2[t], where t6+t+1 is irreducible over F2. [ Often this is written more concise as K = F2[t]/<t6+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) = s2 + (t5 + t2)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, t2, t3, t4, t5 }, 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 = K2 = 642 = 4096 = 212. 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: F2[x]/<x12+x3+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$(1K) = 1L), 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 (k1, k2) where k1 and k2 are elements of (a field isomorphic with) K and the element is actually k1 + k2 $\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 = F2[t]/<t6+t+1> and L = F2[x]/<x12+x3+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 t6+t+1 = 0. If g is a generator of the multiplicative group L* (L without it's zero), then it turns out that t = g65, where 65 comes from L* / K* = 4095 / 63 = 65. The other roots of t6+t+1 = 0 can be found by applying Frobenius repeatedly to g65, 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 = x9 + x8 + x7 + x4 + x2 + x as generator of L (as found by the function generator(void) in point/bspacetables3.cc). t = g65 = x11 + x10 + x8 + x7 + x + 1. Furthermore we have u(s) = s2 + (t5 + t2)s + 1 = 0 $\longrightarrow$ s2 + (x10 + x7 + x6 + x3 + x)s + 1 = 0 $\longrightarrow$ s = x11 + x9 + x8 + x7 + x6 + x5 + 1 or s = x11 + x10 + x9 + x8 + x5 + x3 + x + 1. And indeed, using one of those s, k1 + k2s, where k1 and k2 run from 0 to x5 + x4 + x3 + x2 + x + 1 generates exactly all elements in L from 0 to x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1! So, K[s]/<s2+(t5+t2)s+1> and F2[x]/<x12+x3+1> are the same thing after all!

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

Proof:

Let L = F2m be an extension of the proper subfield K = F2n. This means that n < m and n|m. Let x $\in$ L be such that the smallest integer k such that x2k = x is for k = m, in other words x is in an Frobenius equivalence class size m over F2m. 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, x2d = 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 F22n that are their own inverse is equal to the number of Frobenius equivalence classes size n over F2n, 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 F22n that are not in a proper subfield of F22n and that have an inverse that is also not in a proper subfield of F22n, is equal to twice the number of elements in F2n that are not in a proper subfield of F2n and have trace 1.

Let x $\in$ F2n and y $\in$ F22n. Consider the equation y2 + xy + 1 = 0. This being a quadratic equation with coeficients from F2n, there are three possibilities: 1) The equation has one solution, 2) The equation has no solution over F2n, 3) The equation has two solutions over F2n. 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 F22n always exist: y and 1/y, after all y $\ne$ 0 and (1/y)2 + x/y + 1 = (1 + xy + y2)/y2 = 0. In order for y not to be in a proper subgroup of F22n, the equation may not have solutions over F2n (otherwise y would be in the proper subgroup F2n). Moreover, x may not be in a proper subgroup J of K = F2n (so that [K:J] > 1), because if it were then y would be in a subgroup S such that [S:F2] = [S:J][J:F2] = 2[J:F2] < [L:F2] = [L:K][K:J][J:F2] = 2[K:J][J:F2] 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, y2k = 1/y, as we saw before, with k = n = m/2). Knowing that y + 1/y = x, and since 1/y = y2n, we can write y + y2n = x, and thus see that there will only be solutions over F2n 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 F22n are not in a proper subgroup of F22n if and only if x is not in a proper subgroup of F2n 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 
ANumber of Frobenius equivalence classes (foc(m) / m = A001037): 12369183056991863356301161218240807710145322759452377998581905573647226988701342176258079549710089586395185127903579026769273666
BNumber of Frobenius equivalence classes with trace 1 (blwt1(m) = A000048 (see also proposition 3)): 1123591628519317031558510912048385572801379726214499299532518236134952067108812905552485504479349092563951789567934636833
CNumber of Frobenius equivalence classes that are their own inverse (blwt1(m/2) (propositions 2 and 5)): 1010102030509016028051093017003150585010910
DNumber of Frobenius equivalence classes that are their own inverse with trace 1 (depends on w(m/2, 1)*): 1010001020204090140240480860154029405500
ENumber of generators (euler_phi(2m - 1) / m = A011260): 122661816486017614463075618002048771077762759424000846721200323569602764801296000171990042024964741632184078081782000069273666
FNumber of generators with trace 1 (no formula): 11134972531877231538190110173855389013797120004234460043178431138224648031860059210135323707159203747890894034636833
GNumber of normal basis (num_normal(m) = A027362): 112347162148931283154486752048382553761379724576277839523218218326214462914512902401835001367001692563951105920028629151
HNumber of normal basis that exist of generators (no formula, A107222): 11133771929875231529156210173825287013797112552357959986178259103680607522859849155122718150459203747550596628629151
INumber of solutions, w(m, 1) (this is what we want to know) (A137503): 1014381628459616730857911002018385272801377626133499969522318224834947467117612899252485644479335592557001789442134638296
JNumber of solutions with trace 1 (no formula): 101224914244886154294550101719263654688813092249984765891124174822335588645120124282223969704627850894775617319148
KNumber of solutions that are generators (no formula): 100428102626947630837890210143852390813776119444246060014178414138360648042859642210129023708589202954891028834638296
LNumber of solutions that are generators with trace 1 (no formula): 100224414144638154192452500192619566888597221238300348915869164324052429930105075011853284601320445408417319148
MNumber of solutions that are normal basis (no formula): 10122491222486215422433210171912271268881228613912476109102813109431458464496691760018351444627850552989614314976
NNumber of solutions that are normal basis and generators (no formula): 1002244121346251541452775001912145968885603118763000589062518883037614298297755669076844601320275336114314976

* 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
14
28
34
416
544
656
7116
8288
9508
10968
112116
124144
138012
1416472
1533044
1665088
17130972
18263144
19523492
201047376
212099948
224193912
238383412
2416783200
2533558844
2667092488
27134225284
28268460656
29536830604
301073731736
312147574356
324294896768
338589823708
3417180121128
3534359708196
3668719003024
37137439487532
38274878320312
39549754332404
401099512282528
412199025563772
424398042893384
438796092023492
4417592194278576
4535184365852108
4670368733946072
47140737511060372
48281474974468800
49562949910253084
501125899954494568
512251799852369764
524503599493382096
539007199311360364
5418014398720839416
5536028796694367796
5672057593939809248
57144115188823166908
58288230375600638088
59576460751359875076
601152921506652542704
612305843009055095052
624611686014494595352
639223372041104766164

Of course, much more analysis will follow...

<To Be Continued>

Copyright © 2002-2008 Carlo Wood.  All rights reserved.