Constructing irreducible polynomials recursively with a reverse composition method

Abstract: We suggest a construction of the minimal polynomial

of

over

m a t h b b F_{q}

from the minimal polynomial

for all positive integers

k

whose prime factors divide

q - 1

. The computations of our construction are carried out in

m a t h b b F_{q}

. The key observation leading to our construction is that for

k m i d q - 1

holds

m_{�eta^k}(X^k) = prod_{j=1}^{frac kt} zeta_k^{-jn} f (zeta_k^j X),

where

t = m a x m m i d g c d (n, k) : f (X) = g (X^{m}), g i n m a t h b b F_{q} [X]

and

z e t a_{k}

is a primitive

k

-th root of unity in

m a t h b b F_{q}

. The construction allows to construct a large number of irreducible polynomials over

m a t h b b F_{q}

of the same degree. Since different applications require different properties, this large number allows the selection of the candidates with the desired properties.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Constructing irreducible polynomials recursively with a reverse composition method

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