Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials

MaRDI QIDQ4664835zbMATH OpenFDO

Authors Richard P. Brent, Paul Zimmermann

Publication date 8 April 2005

Full work available at URL https://arxiv.org/abs/2105.06013

zbMATH Keywords

algorithmirreducible trinomialprimitive trinomialSwan's theorem

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16)

Abstract: Consider polynomials over $mGF(2)$. We describe efficient algorithms for finding trinomials with large irreducible (and possibly primitive) factors, and give examples of trinomials having a primitive factor of degree $r$ for all Mersenne exponents $$ in the range $5<r<10^7$, although there is no irreducible trinomial of degree $r$. We also give trinomials with a primitive factor of degree $r=2^k$ for $3lekle12$. These trinomials enable efficient representations of the finite field $mGF(2^r)$. We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.

Recommendations

• scientific article; zbMATH DE number 1047540
• scientific article; zbMATH DE number 1135075
• Search of primitive polynomials over finite fields
• A fast algorithm for testing reducibility of trinomials mod~2 and some new primitive trinomials of degree 3021377
• scientific article; zbMATH DE number 872088

Cited in

(6)

• Computing sparse multiples of polynomials
• A new approach for finding low-weight polynomial multiples
• Koblitz curves over quadratic fields
• scientific article; zbMATH DE number 1135075 (Why is no real title available?)
• A primitive trinomial of degree 6972593
• Binary Kummer line

This page was built for publication: Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4664835)