A190616 - OEIS

%I #23 Oct 30 2023 10:38:04

%S 1,1,1,2,1,4,1,0,3,8,3,16,5,16,15,0,17,48,27,128,63,192,89,0,205,637,

%T 171,1011,565

%N Number of normal bases in GF(2^n) that are Gaussian normal bases.

%C A type-t Gaussian normal basis (GNB) exists for GF(2^n) if p=n*t+1 is prime and gcd(n,(p-1)/ord(2 mod p))==1.  In practice one finds (for fixed n) infinitely many t corresponding to some GNB.  As there are only finitely many normal bases for fixed n the GNBs for different t are not in general different but correspond to a finite set of field polynomials.  This sequence gives the number of field polynomials (equivalently, mod-2 reduced multiplication matrices) that correspond to some GNB.

%C The sequence was computed by determining all field polynomials for types t <= n*500 and discarding duplicate polynomials.  Note that there is no guarantee that the used bound (500*n) leads to discovery of all polynomials.

%C An efficient method to determine (for fixed n) whether two types, say t1 and t2, correspond to the same polynomial would be of great interest.

%C A computation using the bound t<=2000 gave a(22)=192 (the old value was 191), so the sequence was corrected past that term and truncated after a(29). [_Joerg Arndt_, May 16 2011]

%H Joerg Arndt, <a href="https://jjj.de/fxt/#fxtbook">Fxtbook</a>, section 42.9 "Gaussian normal bases", pp. 914-920.

%F a(8*n) = 0 (there is no GNB for multiples of eight).

%e For n=5 there is just one field polynomial (x^5 + x^4 + x^2 + x + 1),

%e   for p in {11, 31, 41, 61, 71, 101, 131, ...} (A040160).

%e For n=7 there is just one field polynomial (x^7 + x^6 + x^4 + x + 1),

%e   for p in {29, 43, 71, 113, 127, 197,...} (A042967).

%e For n=11 there are three GNBs:

%e x^11 + x^10 + x^8 + x^4 + x^3 + x^2 + 1

%e   for p in {23, 463, 661, 859, 881, 1409, 1453, 2179, ...},

%e x^11 + x^10 + x^8 + x^5 + x^2 + x + 1

%e   for p in {67, 89, 353, 727, 947, 1277, 1607, 1783, 1871, ...}, and

%e x^11 + x^10 + x^8 + x^7 + x^6 + x^5 + 1

%e   for p in {199, 397, 419, 617, 683, 991, 1123, 2003, 2069, 2113, ...}.

%K nonn,hard,more

%O 1,4

%A _Joerg Arndt_, May 14 2011