A137503 - OEIS

%I #6 Feb 23 2013 12:42:36

%S 1,0,1,4,3,8,16,28,45,96,167,308,579,1100,2018,3852,7280,13776,26133,

%T 49996,95223,182248,349474,671176,1289925,2485644,4793355,9255700,

%U 17894421,34638296,67105714,130148812,252644985,490852972

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

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

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

%C 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.

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

%C 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.

%C 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.

%H Carlo Wood, <a href="http://libecc.sourceforge.net/reference-manual/group__theory__bspace.html">Cracking parameter b of the elliptic curve</a>.

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

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

%F 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)}.

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

%e Let g be a generator of the multiplicative group GF(2^6)^* with reduction polynomial t^6+t+1 = 0.

%e Pick g = t^3+1 (which generator is chosen doesn't matter for the sequence; but it matters for the table below).

%e 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.

%e These elements are equivalent, any may be chosen as representative.

%e The inverse of the FEC is an FEC with the inverse of those elements (all of which are in the same FEC of course).

%e 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.

%e 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.

%e The trace of the FEC is given after the FEC.

%e .......... x .......... Tr(x) ........ 1/x ........ Tr(1/x)

%e { _1, _2, _4, _8, 16, 32} 0 { 31, 47, 55, 59, 61, 62} 1

%e { _3, _6, 12, 24, 33, 48} 0 { 15, 30, 39, 51, 57, 60} 1

%e { _5, 10, 17, 20, 34, 40} 1 { 23, 29, 43, 46, 53, 58} 1

%e { _7, 14, 28, 35, 49, 56} 0 { _7, 14, 28, 35, 49, 56} 0

%e { 11, 22, 25, 37, 44, 50} 1 { 13, 19, 26, 38, 41, 52} 0

%e { 13, 19, 26, 38, 41, 52} 0 { 11, 22, 25, 37, 44, 50} 1

%e { 15, 30, 39, 51, 57, 60} 1 { _3, _6, 12, 24, 33, 48} 0

%e { 23, 29, 43, 46, 53, 58} 1 { _5, 10, 17, 20, 34, 40} 1

%e { 31, 47, 55, 59, 61, 62} 1 { _1, _2, _4, _8, 16, 32} 0

%e 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.

%Y Cf. A000048, A001037.

%K nonn

%O 2,4

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