A137503 Number of Frobenius equivalence classes of size n over GF(2^n) with their trace equal to the trace of their inverse.

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, 67105714, 130148812, 252644985, 490852972

Offset

2,4

Comments

The number of Frobenius equivalence classes (FEC) of size n is given by A001037.

The trace of an FEC of size n is the sum of its elements.

The trace of (an element of) an FEC with a size d < n is either 0 or the sum of its elements; it is 0 when n/d is even; more generally, Tr(FEC) = Tr(representative) = n/d * sum of all elements in FEC.

The number of FEC with size n and trace 1 is given by sequence A000048.

The number of FEC with size n that is its own inverse (7 in the example below) is zero for odd n and A000048 (with n/2 as index) for even n.

The number of FEC with size n that are their own inverses and have trace 1 is zero if n is odd, is equal to (this sequence with index n/2)/2 if n/2 is odd and equal to (this sequence with index n/2 + A000048 with index n/4)/2 if n/2 is even.

Links

Table of n, a(n) for n=2..35.

Carlo Wood, Cracking parameter b of the elliptic curve.

Formula

Let b(1) = 0, b(2) = 1, b(n) = 2^(n-1) - b(n-1) - 2 * b(n-2) - 3.

Let c(1) = 1, c(n) = 2^(n-1) - sum_{0<d<m,d|m}{c(d)}.

Let w(n) = b(n) - sum_{1<d<m,d even,d|m}{c(n/d)} - sum_{1<d<m,d odd,d|m}{w(n/d)}.

Then a(n) = 2 * w(n) / n.

Example

Let g be a generator of the multiplicative group GF(2^6)^* with reduction polynomial t^6+t+1 = 0.
Pick g = t^3+1 (which generator is chosen doesn't matter for the sequence; but it matters for the table below).
Let n be an integer, 0 < n < 2^6 - 1. Let the smallest positive integer k such that (g^n)^(2^k) = g^n be k = 6, then the elements { g^n, (g^n)^2, (g^n)^(2^2), (g^n)^(2^3), (g^n)^(2^4), (g^n)^(2^5) } are all different and form an FEC with size 6.
These elements are equivalent, any may be chosen as representative.
The inverse of the FEC is an FEC with the inverse of those elements (all of which are in the same FEC of course).
The trace of each element is the same, of course and therefore we might as well speak about the inverse of the FEC and the trace of the FEC respectively.
In the table below, the FEC are denoted as {1,2,4,8,16,32} etc, only giving the exponents of g. All FEC with size 6 are given in both columns, the two columns give each others inverse.
The trace of the FEC is given after the FEC.
.......... x .......... Tr(x) ........ 1/x ........ Tr(1/x)
{ _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
{ 13, 19, 26, 38, 41, 52} 0 { 11, 22, 25, 37, 44, 50} 1
{ 15, 30, 39, 51, 57, 60} 1 { _3, _6, 12, 24, 33, 48} 0
{ 23, 29, 43, 46, 53, 58} 1 { _5, 10, 17, 20, 34, 40} 1
{ 31, 47, 55, 59, 61, 62} 1 { _1, _2, _4, _8, 16, 32} 0
This shows that there are 3 FEC (namely, 5, 7 and 23) whose trace is equal to the trace of its inverse and hence a(6) = 3.

Crossrefs

Cf. A000048, A001037.

Sequence in context: A165739 A196132 A198179 * A320263 A215330 A108624

Adjacent sequences: A137500 A137501 A137502 * A137504 A137505 A137506

Keyword

nonn

Author

Carlo Wood (carlo(AT)alinoe.com), Apr 22 2008, May 01 2008, May 05 2008

Status

approved