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

Author

Max Alekseyev, Feb 11 2008

Keywords

• nonn

Links

• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems
• 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.

Crossrefs

Cf. A088437.

Programs

PARI

/* based on 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 */
{
    my(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 */