Iterative constructions of irreducible polynomials from isogenies

Résumé fourni par la source

Let S be a rational fraction and let f be a polynomial over a finite field. Consider the transform T ( f ) = numerator ( f ( S ) ) . In certain cases, the polynomials f , T ( f ) , T ( T ( f ) ) … are all irreducible. For instance, in odd characteristic, this is the case for the rational fraction S = ( x 2 + 1 ) / ( 2 x ) , known as the R -transform, and for a positive density of irreducible polynomials f . We interpret these transforms in terms of isogenies of elliptic curves. Using complex multiplication theory, we devise algorithms to generate a large number of rational fractions S , each of which yields infinite families of irreducible polynomials for a positive density of starting irreducible polynomials f .