cp's OEIS Frontend

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

%I A137503 #6 Feb 23 2013 12:42:36
%S A137503 1,0,1,4,3,8,16,28,45,96,167,308,579,1100,2018,3852,7280,13776,26133,
%T A137503 49996,95223,182248,349474,671176,1289925,2485644,4793355,9255700,
%U A137503 17894421,34638296,67105714,130148812,252644985,490852972
%N A137503 Number of Frobenius equivalence classes of size n over GF(2^n) with their trace equal to the trace of their inverse.
%C A137503 The number of Frobenius equivalence classes (FEC) of size n is given by A001037.
%C A137503 The trace of an FEC of size n is the sum of its elements.
%C A137503 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 A137503 The number of FEC with size n and trace 1 is given by sequence A000048.
%C A137503 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 A137503 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 A137503 Carlo Wood, <a href="http://libecc.sourceforge.net/reference-manual/group__theory__bspace.html">Cracking parameter b of the elliptic curve</a>.
%F A137503 Let b(1) = 0, b(2) = 1, b(n) = 2^(n-1) - b(n-1) - 2 * b(n-2) - 3.
%F A137503 Let c(1) = 1, c(n) = 2^(n-1) - sum_{0<d<m,d|m}{c(d)}.
%F A137503 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 A137503 Then a(n) = 2 * w(n) / n.
%e A137503 Let g be a generator of the multiplicative group GF(2^6)^* with reduction polynomial t^6+t+1 = 0.
%e A137503 Pick g = t^3+1 (which generator is chosen doesn't matter for the sequence; but it matters for the table below).
%e A137503 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 A137503 These elements are equivalent, any may be chosen as representative.
%e A137503 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 A137503 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 A137503 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 A137503 The trace of the FEC is given after the FEC.
%e A137503 .......... x .......... Tr(x) ........ 1/x ........ Tr(1/x)
%e A137503 { _1, _2, _4, _8, 16, 32} 0 { 31, 47, 55, 59, 61, 62} 1
%e A137503 { _3, _6, 12, 24, 33, 48} 0 { 15, 30, 39, 51, 57, 60} 1
%e A137503 { _5, 10, 17, 20, 34, 40} 1 { 23, 29, 43, 46, 53, 58} 1
%e A137503 { _7, 14, 28, 35, 49, 56} 0 { _7, 14, 28, 35, 49, 56} 0
%e A137503 { 11, 22, 25, 37, 44, 50} 1 { 13, 19, 26, 38, 41, 52} 0
%e A137503 { 13, 19, 26, 38, 41, 52} 0 { 11, 22, 25, 37, 44, 50} 1
%e A137503 { 15, 30, 39, 51, 57, 60} 1 { _3, _6, 12, 24, 33, 48} 0
%e A137503 { 23, 29, 43, 46, 53, 58} 1 { _5, 10, 17, 20, 34, 40} 1
%e A137503 { 31, 47, 55, 59, 61, 62} 1 { _1, _2, _4, _8, 16, 32} 0
%e A137503 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 A137503 Cf. A000048, A001037.
%K A137503 nonn
%O A137503 2,4
%A A137503 Carlo Wood (carlo(AT)alinoe.com), Apr 22 2008, May 01 2008, May 05 2008