login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A190616 Number of normal bases in GF(2^n) that are Gaussian normal bases. 0
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, 171, 1011, 565 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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.

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.

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.

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]

LINKS

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

Joerg Arndt, Fxtbook, section 42.9 "Gaussian normal bases", pp.914-920.

FORMULA

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

EXAMPLE

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

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

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

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

For n=11 there are three GNBs:

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

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

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

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

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

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

CROSSREFS

Sequence in context: A295881 A117971 A220420 * A238018 A131642 A070674

Adjacent sequences:  A190613 A190614 A190615 * A190617 A190618 A190619

KEYWORD

nonn,hard,more

AUTHOR

Joerg Arndt, May 14 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 15 14:38 EDT 2019. Contains 327078 sequences. (Running on oeis4.)