Factorization of polynomials over finite fields: Difference between revisions

Revision as of 00:16, 4 November 2018

Revision as of 16:17, 4 November 2018

Line 22:

Irreducible polynomials over finite fields are also useful for [[Pseudorandom]] number generators using feedback shift registers and [[discrete logarithm]] over '''F'''_2^''n''.

The number of primary (i.e. power of an irreducible) [[monic polynomial]]s of degree ''n'' over '''F'''_''q'' is equal to the [[Necklace (combinatorics)|necklace counting functionpolynomial]] ''N''_''q''(''n'').<ref>Christophe Reutenauer, ''Mots circulaires et polynomes irreductibles'', Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285</ref> Alternatively, one may consider this as the number of irreducible polynomials of all degrees d dividingwhich divide n;.

The number of irreducible monic polynomials of degree exactly n is the number of [[Necklace (combinatorics)#Aperiodic necklaces|aperioidic necklaces]], given by [[Necklace polynomial|Moreau's polynomial]] M_''q''(''n'').

to get the number of irreducibles of degree exactly n, one applies [[Mobius inversion formula|Mobius inversion]].

==== Example= ===

The polynomial ''P'' = ''x''⁴ + 1 is irreducible over '''Q''' but not over any finite field.