A135488 Number of distinct self-dual normal bases for GF(2^n) over GF(2)

1, 1, 1, 0, 1, 2, 1, 0, 3, 4, 3, 0, 5, 8, 15, 0, 17, 48, 27, 0, 63, 96, 89, 0, 205, 320, 513, 0, 565, 1920, 961, 0, 3267, 4352, 4095, 0, 7085, 13824, 20475, 0, 25625, 64512, 49923, 0, 184275, 182272, 178481, 0, 299593, 839680, 1105425, 0, 1266205, 4202496, 3145725, 0, 7105563, 9256960, 9099507, 0

Offset

1,6

Links

Table of n, a(n) for n=1..60.

Max Alekseyev, PARI scripts

Joerg Arndt, Matters Computational (The Fxtbook), see p. 910.

Dieter Jungnickel, Alfred J. Menezes and Scott A. Vanstone, On the Number of Self-Dual Bases of GF(q^m) Over GF(q), Proc. Amer. Math. Soc. 109 (1990), 23-29.

Prog

(PARI)
/* based on http://home.gwu.edu/~maxal/gpscripts/nsdb.gp by Max Alekseyev */
sdn(m, p) =
/* Number of distinct self-dual normal bases of GF(p^m) over GF(p) where p is prime */
{
    local(F, f, g, s, c, d);
    if ( p==2 && m%4==0, return(0) );
    if ( !(m%p), /* p divides m */
        s = m\p;
        return( p^((p-1)*(s+(s*(p+1))%2)/2-1) * sdn(s, p) );
    , /* else */
        F = factormod( (x^m - 1)/(x - 1), p );
        c = d = [];
        for (i=1, matsize(F)[1],
            f = lift(F[i, 1]);
            g = polrecip(f);
            if ( f==g,  c = concat( c, vector(F[i, 2], j, poldegree(f)/2) ); );
            if ( lex(Vec(f), Vec(g))==1 ,
                d = concat( d, vector(F[i, 2], j, poldegree(f)) );
            );
        );
        return( 2^(p%2) * prod(i=1, #c, p^c[i] + 1) * prod(j=1, #d, p^d[j] - 1) / m );
    );
}
vector(66, n, sdn(n, 2)) /* Joerg Arndt, Jul 03 2011 */

Crossrefs

Cf. A088437.

Sequence in context: A094301 A221542 A221463 * A099493 A088523 A222211

Adjacent sequences: A135485 A135486 A135487 * A135489 A135490 A135491

Keyword

nonn

Author

Max Alekseyev, Feb 11 2008

Status

approved