De Fp X Z X remontée de Hensel

Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 48
Source : math.unice.fr
Nombre de pages : 15
Voir plus Voir moins
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
( x 6 62 # 45 x 5 8 x 4 93 x 3 # 92 x 2 # 43 x ) > Factor(P) mod 23; ( x 6 # 10 x 5 # 10 x 4 # 3 x 3 # 17 x 2 # 11 x # 10 ) ( x 6 # 22 x 5 # 15 x 4 # 22 x 3 # 20 x # 7 ) > R:=x^6+10*x^5+10*x^4+3*x^3+17*x^2+11*x+10;S:=x^6+22*x^5+15*x^ 4+22*x^3+20*x+7; R := x 6 # 10 x 5 # 10 x 4 # 3 x 3 # 17 x 2 # 11 x # 10 S := x 6 # 22 x 5 # 15 x 4 # 22 x 3 # 20 x # 7 > HenselLin2Fact(R,S,23,P,true); "Borne =", 2417192 3658 6071 x 6952 x 5 398 x 4 # 10402 x 3 6883 x 2 # 5932 x 6 # x 12 # 124 x 11 # 3603 x 10 # 1844 x 9 5435 x 8 # 4603 x 7 1 ( x 6 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x # 470 ) ( x 6 # 45 x 5 # 521 x 4 # 436 x 3 # 43 x # 467 # 92 x 2 ), "mod", 529 3658 6071 x 6952 x 5 398 x 4 # 10402 x 3 6883 x 2 # 5932 x 6 # x 12 # 124 x 11 # 3603 x 10 # 1844 x 9 5435 x 8 # 4603 x 7 1 ( x 6 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x # 12108 ) ( x 6 # 45 x 5 # 12159 x 4 # 12074 x 3 # 43 x # 12105 # 92 x 2 ), "mod", 12167 3658 6071 x 6952 x 5 398 x 4 # 10402 x 3 6883 x 2 # 5932 x 6 # x 12 # 124 x 11 # 3603 x 10 # 1844 x 9 5435 x 8 # 4603 x 7 1 ( x 6 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x # 279782 ) ( x 6 # 45 x 5 # 279833 x 4 # 279748 x 3 # 43 x # 279779 # 92 x 2 ), "mod", 279841 11 3658 6071 x 6952 x 5 398 x 4 # 10402 x 3 6883 x 2 # 5932 x 6 # x 12 # 124 x # 3603 x 10 # 1844 x 9 5435 x 8 # 4603 x 7 1 ( x 6 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x # 6436284 ) ( 6 # 45 x 5 # 6436335 x 4 # 6436250 x 3 # 43 x # 6436281 # 92 x 2 ), "mod", 6436343 x x 6 59 # 79 x 5 # 56 x 4 # 49 x 3 # 63 x 2 # 57 x , x 6 62 # 45 x 5 8 x 4 93 x 3 # 92 x 2 # 43 x On retrouve les bons facteurs dans Z. La borne de Landau-Mignotte est pessimiste mais ça tient la méthode de construction de P, produit de deux polynômes à coefficients assez petits. Maintenant un essai avec deux facteurs au départ, un seul à l'arrivée. > P:=x^12+randpoly(x,degree=11,dense); P : x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 = 50 x > factor(P); x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x > Factor(P) mod 5; ( x 6 # 4 x 3 # 2 x 2 # 2 ) ( x 6 # 2 x 5 # 2 x 4 # 4 x 3 # 3 x 2 # 4 ) > R:=x^6+4*x^3+2*x^2+2;S:=x^6+2*x^5+2*x^4+4*x^3+3*x^2+4; 3 R := x 6 # 4 x # 2 x 2 # 2
6 S := x # 2 x 5 # 2 x 4 # 4 x 3 # 3 x 2 # 4 > HenselLin2Fact(R,S,5,P,true); "Borne =", 29246 12 x 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 14 x 3 # 17 x 2 # 2 # 20 x 5 # 20 x 4 # 15 x ) ( x 6 # 12 x 5 # 7 x 4 # 24 x 3 # 8 x 2 # 19 # 20 x ), "mod", 25 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 114 x 3 # 117 x 2 # 102 # 45 x 5 # 45 x 4 # 65 x ) ( x 6 # 112 x 5 # 7 x 4 # 74 x 3 # 33 x 2 # 44 # 45 x ), "mod", 125 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 489 x 3 # 117 x 2 # 477 # 45 x 5 # 545 x 4 # 315 x ) ( x 6 # 487 x 5 # 132 x 4 # 74 x 3 # 158 x 2 # 169 # 170 x ), "mod", 625 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 2364 x 3 # 742 x 2 # 1727 # 1920 x 5 # 3045 x 4 # 1565 x ) ( x 6 # 1112 x 5 # 2632 x 4 # 1949 x 3 # 1408 x 2 # 2669 # 795 x ), "mod", 3125 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 11739 x 3 # 13242 x 2 # 1727 # 11295 x 5 # 15545 x 4 # 10940 x ) ( x 6 # 4237 x 5 # 2632 x 4 # 5074 x 3 # 7658 x 2 # 2669 # 3920 x ), "mod", 15625 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x 1 ( x 6 # 11739 x 3 # 60117 x 2 # 17352 # 26920 x 5 # 31170 x 4 # 57815 x ) ( x 6 # 51112 x 5 # 49507 x 4 # 36324 x 3 # 54533 x 2 # 49544 # 50795 x ), "mod", 78125 x 12 12 93 x 11 # 92 x 10 # 43 x 9 62 x 8 # 77 x 7 # 66 x 6 # 54 x 5 5 x 4 # 99 x 3 61 x 2 50 x Les facteurs trouvés modulo 78125 1 5 7  ne marchent pas dans Z. P  est irréductible.
Hensel quadratique, deux facteurs unitaires initiaux
On va maintenant comparer à une version quadratique de la remontée de Hensel : à chaque étap il faut remonter la factorisation et la relation de Bézout. > HenselQuad2Fact:=proc(R,S,p,P,Trace) local R1,S1,U,V,pk,Borne,Defaut1,Rcor,Scor,Defaut2,Ucor,Vcor; R1:=R;S1:=S;Gcdex(R1,S1,x, U','V') mod p;pk:=p; ' if Trace then print(P = R1 * S1,"mod",pk) end if; if Trace then print(R1*U + S1*V=1,"mod",pk) end if; Borne:=2*LandauMignotte(P,max(degree(R1),degree(S1))); if Trace then print("Borne =",Borne) end if; while pk< Borne do Defaut1:=expand((P-R1*S1)/pk); Rcor:=Rem(V*Defaut1,R1,x) mod pk;
Scor:=Rem(U*Defaut1,S1,x) mod pk; Defaut2:=expand((1-(R1*U+S1*V))/pk-(U*Rcor+V*Scor)); Ucor:=Rem(U*Defaut2,S1,x) mod pk; Vcor:=Rem(V*Defaut2,R1,x) mod pk; R1:=R1+pk*Rcor;S1:=S1+pk*Scor; U:=U+pk*Ucor;V:=V+pk*Vcor; pk:=pk*pk; if Trace then print(P = R1 * S1,"mod",pk) end if; if Trace then print(R1*U + S1*V=1,"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: Pour faire un test significatif il faut que la borne à atteindre soit grande. On tire au hasard deux polynômes unitaires ayant des coefficients entre 10 6  et 10 6  . > P1:=x^6+randpoly(x,coeffs=rand(-1000000..1000000));P2:=x^6+ra ndpoly(x,coeffs=rand(-1000000..1000000)); P1 := x 6 549893 751741 x 5 527319 x 4 # 989495 x 3 404225 x 2 # 86737 x P2 := x 6 338018 361478 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x > P:=expand(P1*P2); P := 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4  789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 > 2*LandauMignotte(P,6); 228045014200000 Effectivement la borne commence à être conséquente.
On vérifie que P  n'a que deux facteurs dans Z. > factor(P); ( x 6 549893 751741 x 5 527319 x 4 # 989495 x 3 404225 2 # 86737 x ) x ( x 6 338018 361478 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x ) Quand on tire des polynômes au hasard ils sont en général irréductibles mais ça peut être faux. En tâtonnant on cherche un modulo tel qu'on n'ait que deux facteurs. > Factor(P) mod 7; ( x 6 # 3 x 5 # 5 x 4 # 3 x 3 # 4 x 2 # 6 ) ( x 6 # 2 x 5 # 6 x 4 # x 3 # 2 x 2 # 3 x # 5 ) Voilà donc la factorisation intiale qu'il va falloir remonter jusqu'à 228045014200000 !
> R:=x^6+3*x^5+5*x^4+3*x^3+4*x^2+6;S:=x^6+2*x^5+6*x^4+x^3+2*x^2 +3*x+5; R := x 6 # 3 x 5 # 5 x 4 # 3 x 3 # 4 x 2 # 6 S := x 6 # 2 x 5 # 6 x 4 # x 3 # 2 x 2 # 3 x # 5 et c'est parti > HenselLin2Fact(R,S,7,P,true); "Borne =", 228045014200000
540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 17 x 5 # 19 x 4 # 38 x 3 # 25 x 2 # 7 x # 34 ) ( x 6 # 44 x 5 # 34 x 4 # 36 x 3 # 9 x 2 # 38 x # 33 ) , "mod", 49 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 115 x 5 # 215 x 4 # 283 x 3 # 172 x 2 # 301 x # 279 ) ( x 6 # 44 x 5 # 279 x 4 # 85 x 3 # 205 x 2 # 136 x # 180 ), "mod", 343 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 2173 x 5 # 901 x 4 # 283 x 3 # 1544 x 2 # 301 x # 2337 ) ( 6 # 1073 x 5 # 2337 x 4 # 428 x 3 # 1577 x 2 # 479 x # 523 ), "mod", 2401 x 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 4574 x 5 # 10505 x 4 # 14689 x 3 # 15950 x 2 # 2702 x # 4738 ) ( x 6 # 8276 x 5 # 16743 x 4 # 12433 x 3 # 11181 x 2 # 5281 x # 14929 ), "mod", 16807 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 71802 x 5 # 60926 x 4 # 48303 x 3 # 66371 x 2 # 86737 x # 38352 ) ( x 6 # 109118 x 5 # 33550 x 4 # 46047 x 3 # 11181 x 2 # 106123 x # 14929 ), "mod", 117649 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 x ( x 6 # 71802 x 5 # 296224 x 4 # 165952 x 3 # 419318 x 2 # 86737 x # 273650 ) ( x 6 # 462065 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 106123 x # 485525 ), "mod", 823543 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 5013060 x 5 # 5237482 x 4 # 989495 x 3 # 5360576 x 2 # 86737 x # 5214908 )
( x 6 # 5403323 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 5426783 ), "mod", 5764801 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 39601866 x 5 # 39826288 x 4 # 989495 x 3 # 39949382 x 2 # 86737 x # 39803714 ) ( x 6 # 39992129 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 40015589 ), "mod", 40353607 4 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 281723508 x 5 # 281947930 x 4 # 989495 x 3 # 282071024 x 2 # 86737 x # 281925356 ) ( x 6 # 282113771 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 282137231 ), "mod", 282475249 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 1976575002 x 5 # 1976799424 x 4 # 989495 x 3 # 1976922518 x 2 # 86737 x # 1976776850 ) ( x 6 # 1976965265 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 1976988725 ), "mod", 1977326743 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( 6 x # 13840535460 x 5 # 13840759882 x 4 # 989495 x 3 # 13840882976 x 2 # 86737 x # 13840737308 ) ( x 6 # 13840925723 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 13840949183 ), "mod", 13841287201 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4 789102316578 x 3 # 146429050702 x 2 # x 12 1113219 x 11 # 271737810025 x 10 188371847513 x 9 # 461802603169 x 7 839969003803 x 6 # 185873732074 1 ( x 6 # 96888258666 x 5 # 96888483088 x 4 # 989495 x 3 # 96888606182 x 2 # 86737 x # 96888460514 ) ( x 6 # 96888648929 x 5 # 504146 x 4 # 163696 x 3 # 128830 x 2 # 929666 x # 96888672389 ), "mod", 96889010407 540535493004 x 746583708315 x 8 # 67680402590 x 5 # 783039009236 x 4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.