Preprint: pdf (184K).
Technical Report: pdf (248K).
As an application we give a fast algorithm to search for all irreducible trinomials xr + xs + 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(r2) per trinomial, thus O(r3) 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(r2 (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
For earlier, related results see [199, 214, 233].
For software, see the gf2x package.