Factorization of polynomials over finite fields: Difference between revisions

Revision as of 00:02, 4 November 2018

Revision as of 00:16, 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'''_''pq'' (for ''p'' prime) is equal to the [[Necklace (combinatorics)|necklace counting function]] ''N''_''pq''(''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 dividing n;

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

====Example====