Twelve new primitive binary trinomials

Richard P Brent (1) , Paul Zimmermann (2)

1 MSI - Mathematical Sciences Institute
2 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms

We exhibit twelve new primitive trinomials over GF(2) of record degrees 42 643 801, 43 112 609, and 74 207 281. In addition we report the first Mersenne exponent not ruled out by Swan's theorem [10] — namely 57 885 161 — for which none primitive trinomial exists. This completes the search for the currently known Mersenne prime exponents.

Mots clés: GF(2)[x]; trinomials; irreducible polynomials; primitive polynomials; Mersenne numbers

Domaines: Algorithme et structure de données [cs.DS]

Richard P Brent, Paul Zimmermann. Twelve new primitive binary trinomials. 2016. ⟨hal-01378493⟩