Efficient Arithmetic in Successive Algebraic Extension Fields Using Symmetries

Sébastien Orange (1) , Guénaël Renault (2) , Kazuhiro Yokoyama (3)

1 LMAH - Laboratoire de Mathématiques Appliquées du Havre
2 PolSys - Polynomial Systems
3 Department of Mathematics [Rikkyo]

In this article, we present new results for efficient arithmetic operations in a number field K represented by successive extensions. These results are based on multi-modular and evaluation-interpolation techniques. We show how to use intrinsic symmetries in order to increase the efficiency of these techniques. Applications to splitting fields of univariate polynomials are presented.

Domaines: Calcul formel [cs.SC]

Sébastien Orange, Guénaël Renault, Kazuhiro Yokoyama. Efficient Arithmetic in Successive Algebraic Extension Fields Using Symmetries. Mathematics in Computer Science, 2012, 6 (3), pp.217-233. ⟨10.1007/s11786-012-0112-y⟩. ⟨hal-00777860v2⟩