Content deleted Content added
sp |
Sushidude21! (talk | contribs) No edit summary |
||
Line 19:
Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power ''q'', let '''F'''<sub>''q''</sub> be the finite field with ''q'' elements, unique up to isomorphism. A polynomial ''f'' of degree ''n'' greater than one, which is irreducible over '''F'''<sub>''q''</sub>, defines a field extension of degree ''n'' which is isomorphic to the field with ''q''<sup>''n''</sup> elements: the elements of this extension are the polynomials of degree lower than ''n''; addition, subtraction and multiplication by an element of '''F'''<sub>''q''</sub> are those of the polynomials; the product of two elements is the remainder of the division by ''f'' of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see [[Polynomial greatest common divisor|Arithmetic of algebraic extensions]]).
It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape ''x''<sup>''n''</sup> + ''ax'' + ''b''.{{Citation needed|date=February 2014}}<ref>{{Cite web |title=Reducibility over $\mathbb{Z}_2$? |url=https://math.stackexchange.com/questions/28281/reducibility-over-mathbbz-2 |access-date=2023-09-10 |website=Mathematics Stack Exchange |language=en}}</ref>
Irreducible polynomials over finite fields are also useful for [[pseudorandom]] number generators using feedback shift registers and [[discrete logarithm]] over '''F'''<sub>2<sup>''n''</sup></sub>.
| |||