Affordable Access

Factorisation sur $\mathbb{Z}[X]$ des polynômes de degré élevé à l'aide d'un monomorphisme

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

Factorisation sur Z[X] des polynômes de degré élevé à l'aide d'un monomorphisme INFORMATIQUE THÉORIQUE ET APPLICATIONS GUYVIRY Factorisation surZ[X ] des polynômes de degré élevé à l’aide d’unmonomorphisme Informatique théorique et applications, tome 24, no 4 (1990), p. 387- 407. <http://www.numdam.org/item?id=ITA_1990__24_4_387_0> © AFCET, 1990, tous droits réservés. L’accès aux archives de la revue « Informatique théorique et applications » im- plique l’accord avec les conditions générales d’utilisation (http://www.numdam. org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 24, n° 4, 1990, p. 387 à 407) FACTORISATION SUR Z[X\ DES POLYNÔMES DE DEGRÉ ÉLEVÉ À L'AIDE D'UN MONOMORPHISME (*) par Guy VIRY O Communiqué par J. BERSTEL Résumé. - Le but de cet article est d'améliorer un algorithme défini dans [7]. Cet algorithme utilise un monomorphisme qui transforme tout produit en somme. Grâce à ce monomorphisme on obtient un critère améliorant la recherche des diviseurs d'un polynôme de Z[X] à partir de ses diviseurs sur Z/(pm)[X]. Notons P le polynôme donné de Z [X], d son degré et r le nombre de ses facteurs sur Z/(p) [X\. Dans l'algorithme usuel, défini par Wang dans [8], le coût est dominé par le calcul de 2T produits de polynômes, ce qui donne 2r # (d+Log\\a0 P\\)2. Avec le nouvel algorithme, le facteur (^+Log| |«0 JP| |)2 est remplacé par 2 + Log\\P\\. Mais, comme les calculs doivent être effectués modulo un nombre pm supérieur à (4|| P| |)d , le coût n'est meilleur que si d est suffisamment grand, par rapport à \\P\\. Abstract. - We improve an algorithm that is defined in [7]. This algorithm uses a monomorphi

There are no comments yet on this publication. Be the first to share your thoughts.