De Fp X Z X remontée de Hensel

Description

De Fp [X] à Z[X] : remontée de Hensel Tiens, pas de bibliothèque d'algèbre linéaire. Hensel linéaire, deux facteurs unitaires initiaux On commence par programmer l'utile borne de Landau-Mignotte. > LandauMignotte:=proc(P,q) ceil(2^q*abs(lcoeff(P))*evalf(sqrt(add(coeff(P,x,i)^2,i=0..de gree(P))))) end proc: Je n'ai pas utilisé le coefficient principal bq du facteur Q car on va l'utiliser avec des facteurs unitaires. J'ai rajouté ceil pour prendre l'entier immédiatement supérieur. Les paramètres : P est un polynôme unitaire de Z[x] qui se décompose en les facteurs irréductibles et unitaires =P modR S p . Ceci est supposé vrai et n'est pas testé. Le booléen Trace permet d'activer/désactiver une trace. Les polynômes sont en la variable x . > HenselLin2Fact:=proc(R,S,p,P,Trace) local R1,S1,U,V,pk,Borne,Defaut,Rcor,Scor; R1:=R;S1:=S;Gcdex(R1,S1,x,'U','V') mod p;pk:=p; Borne:=2*LandauMignotte(P,max(degree(R1),degree(S1))); if Trace then print(Borne =,Borne) end if; while pk< Borne do Defaut:=expand

• version quadratique de la remontée de hensel


• x2? ?


• bibliothèque d'algèbre linéaire


• borne de landau-mignotte


• polynôme unitaire dans z


• landaumignotte:=proc


• unitaires initiaux

Informations

• Publié par: pefav
• Nombre de lectures: 56
• Langue: Français

Extrait

De F [X] à Z[X] : remontée de Hensel p

Tiens, pas de bibliothèque d'algèbre linéaire.

Hensel linéaire, deux facteurs unitaires initiaux

On commence par programmer l'utile borne de Landau-Mignotte. > LandauMignotte:=proc(P,q) ceil(2^q*abs(lcoeff(P))*evalf(sqrt(add(coeff(P,x,i)^2,i=0..de gree(P))))) end proc: Je n'ai pas utilisé le coefficient principal b q  du facteur Q  car on va l'utiliser avec des facteurs unitaires. J'ai rajouté ceil pour prendre l'entier immédiatement supérieur. Les paramètres : P  est un polynôme unitaire de Z[x] qui se décompose en les facteurs irréductibles et unitaires P 1 R S mod p  . Ceci est supposé vrai et n'est pas testé. Le booléen Trace permet d'activer/désactiver une trace. Les polynômes sont en la variable x    . > HenselLin2Fact:=proc(R,S,p,P,Trace) local R1,S1,U,V,pk,Borne,Defaut,Rcor,Scor; R1:=R;S1:=S;Gcdex(R1,S1,x,'U','V') mod p;pk:=p; Borne:=2*LandauMignotte(P,max(degree(R1),degree(S1))); if Trace then print("Borne =",Borne) end if; while pk< Borne do Defaut:=expand((P-R1*S1)/pk); Rcor:=Rem(V*Defaut,R,x) mod p; Scor:=Rem(U*Defaut,S,x) mod p; R1:=R1+pk*Rcor;S1:=S1+pk*Scor;pk:=pk*p; if Trace then print(P = R1 * S1,"mod",pk) end if end do; R1:=mods(R1,pk);S1:=mods(S1,pk); if rem(P,R1,x)=0 then R1,S1 else P end if end proc: Remarque : après avoir calculé Rcor on pourrait utiliser le quotient de la division effectuée pour calculer Scor sans division. Un test avec deux facteurs unitaires au départ et deux facteurs unitaires à l'arrivée. > P1:=x^6+randpoly(x);P2:=x^6+randpoly(x); P1 := x 6 − 59 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x P2 := x 6 − 62 # 45 x 5 − 8 4 − 93 x 3 # 92 x 2 # 43 x x > P:=expand(P1*P2);factor(P); P := 3658 − 6071 x − 6952 x 5 − 398 x 4 # 10402 x 3 − 6883 x 2 # 5932 x 6 # x 12 # 124 x 11 8 # 3603 x 10 # 1844 x 9 − 5435 x # 4603 x 7 ( x 6 − 59 # 79 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x ) x