Algorithms for finding almost irreducible and almost primitive trinomials (original) (raw)
Communication Dans Un Congrès Année : 2003
Résumé
Consider polynomials over GF(2)\GF(2)GF(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 r=pm3mmod8r = \pm 3 \mmod 8r=pm3mmod8 in the range 5<r<1075 < r <10^75<r<107, although there is no irreducible trinomial of degree~$r$. We also give trinomials with a primitive factor of degree r=2kr = 2^kr=2k for 3lekle123 \le k \le 123lekle12. These trinomials enable efficient representations of the finite field GF(2r)\GF(2^r)GF(2r). We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.
Dates et versions
inria-00099724 , version 1 (26-09-2006)
Identifiants
- HAL Id : inria-00099724 , version 1
- ARXIV : 2105.06013
Citer
Richard P. Brent, Paul Zimmermann. Algorithms for finding almost irreducible and almost primitive trinomials. Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams, 2003, Banff, Canada, France. ⟨inria-00099724⟩
310 Consultations
0 Téléchargements