The R-transform as a power map and its generalisations to higher degree

2019/09/05 by Alp Bassa, Ricardo Menares, Bassa, Alp +1
Computer Science · #Coding theory and cryptography #Digital Filter Design and Implementation #Cryptography and Residue Arithmetic

paper · pdf · doi:10.48550/arxiv.1909.02608

Abstract

We give iterative constructions for irreducible polynomials over F_q of degree nt^r for all nonnegative integers r, starting from irreducible polynomials of degree n. The iterative constructions correspond modulo fractional linear transformations to compositions with power functions x^t. The R-transform introduced by Cohen is recovered as a particular case corresponding to x², hence we obtain a generalization of Cohen's R-transform (t=2) to arbitrary degrees t bigger that two. Important properties like self-reciprocity and invariance of roots under certain automorphisms are deduced from invariance under multiplication by appropriate roots of unity. Extending to quadratic extensions of F_q we recover and generalize a recently obtained recursive construction of Panario, Reis and Wang.

Related

• Iterated constructions of completely normal polynomials
• Iterative constructions of irreducible polynomials from isogenies
• Sequences of irreducible polynomials over odd prime fields via elliptic curve endomorphisms, II
• Construction of irreducible polynomials through rational transformations
• Polynomials, roots, and interlacing