Primitive Polynomial (field Theory) - Primitive Trinomials

Primitive Trinomials

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms, because they are the simplest and result in the most efficient pseudo-random number generators. A number of results give techniques for locating and testing primitiveness of trinomials.

For trinomials over GF(2), there is a simple test: for every r such that 2r − 1 is a Mersenne prime, a trinomial of degree r is primitive if and only if it is irreducible. Recent algorithms invented by Richard Brent have enabled the discovery of primitive trinomials over GF(2) of very large degree, such as x6972593 + x3037958 + 1. This can be used to create a pseudo-random number generator of the huge period 26972593 − 1, or roughly 102098959.