x]/*P(x)* of certain *interval polynomials*
when *P(x)* is sparse.
As an application we give a fast
algorithm to search for all irreducible trinomials
*x*^{r} + x^{s} + 1 of degree
*r* over GF(2), while producing a certificate that can be checked
in less time than the full search.
Naive algorithms cost *O(r*^{2}) per trinomial,
thus *O(r*^{3}) to search
over all trinomials of given degree *r*.
Under a plausible assumption about the
distribution of factors of trinomials, the new algorithm has
complexity *O(r*^{2} (log*
r)*^{3/2}(log\log* r)*^{1/2})
for the search over all trinomials of degree *r*.
Our implementation achieves a speedup of greater than a factor
of 560 over the naive algorithm
in the case *r* = 24036583 (a Mersenne exponent).

Using our program, we have found two new primitive trinomials
of record degree 24036583 over GF(2) (the
previous record degree was
6972593). The two new primitive trinomials of degree 24036583 are

*x*^{24036583} + *x*^{8412642} + 1
and
*x*^{24036583} + *x*^{8785528} + 1.

## Comments

For more recent results, see
[235].
For earlier, related results see
[199,
214,
233].

For software, see the gf2x
package.

Go to next publication

Return to Richard Brent's index page