# TP 3 : Factorisation bivariée dans Q[t,x]

## Exercice 1 : Test unitaire séparable modulo (t).

### Fonction test

Test(F):=block(
    [f],
    if coeff(F,x,hipow(F,x))#1 then 
        (print("non unitaire"),
        return(false)),
    f:ev(F,t:0),
    if hipow(gcd(f,diff(f,x)),x)#0 then 
        (print("non séparable modulo (t)"),
        return(false)),
    return(true)
);

Test(2*x**2+t*x+t);

### Polynôme test

F1:x**2+t*x-1; F2:x**3+3*x*t**3-3*x*t+t**2-8; F3:x**3+2*x**2*t**3-t**2*x+t**4+2;

ex:expand(F1*F2*F3);

factor(ex);

factor(ev(ex,t:0));

Test(ex);

## Exercice 2 : Remontée de Hensel de F=GH

### Fonction modulo (t**k)

Mod(F,k):=block(return(remainder(F,t**k)));

Mod(ex,4);

### EtapeHensel

Si F=gh mod (t) et gu+hv=1 mod (t^k), avec h monique , deg(g)+deg(h)=deg(f) et deg(u)<deg(h), deg(v)< deg(g),

EtapeHensel renvoie une liste [gg,hh,uu,vv] avec F=gg * hh mod (t^(2k)) et gg*uu+hh*vv=1 mod (t^(2k)) 

et avec hh monique , deg(gg)+deg(hh)=deg(f) et deg(uu)<deg(hh), deg(vv)< deg(gg) 

EtapeHensel(F,g,h,u,v,k) := block(
    [e,q,r,gg,hh,b,qq,rr,uu,vv],
    
    e : Mod(F-g*h,2*k),
    q: Mod(quotient(u*e,h,x),2*k),
    r: Mod(remainder(u*e,h,x),2*k),
    gg : Mod(g + v*e+q*g,2*k),
    hh : Mod(h + r,2*k),
    b : Mod(v*hh+u*gg-1,2*k),
    qq : Mod(quotient(u*b,hh,x),2*k),
    rr : Mod(remainder(u*b,hh,x),2*k),
    uu : Mod(u-rr,2*k),
    vv : Mod(v-v*b-qq*gg,2*k),
    return([gg,hh,uu,vv]) 
)$

### Hensel

En itérant EtapeHensel, on lifte modulo t^(2^n).

Hensel(F,g,h,u,v,n) := block(
    [l,k],
    if n=0 then
        return([g,h,u,v]),
    if Mod(u*g+v*h,1) # 1 then 
        (print ("mauvaise identité de bezout"),
        return ()),
    l:EtapeHensel(F,g,h,u,v,1),
    k:1,
    for i:1 thru n-1 do
        (k:2*k,
        l:EtapeHensel(F,l[1],l[2],l[3],l[4],k)),
    return (l)
)$

 Tests 

n:3;
g:Mod(F1*F2,1);
h:Mod(F3,1);
u:expand(gcdex(g,h,x)[1]);
v:expand(gcdex(g,h,x)[2]);

E:EtapeHensel(ex,g,h,u,v,1);

Mod(ex-E[1]*E[2],2); Mod(E[1]*E[3]+E[2]*E[4],2);

l:Hensel(ex,g,h,u,v,2)$

ex-l[1]*l[2];

Mod(ex-l[1]*l[2],4);

## Exercice 3 : Facto modulaire

### Liste des facteurs modulo (t)

LMod(F):=block(
     [f,L],
     f:Mod(F,1),   
     L:args(factor(f)),
     if hipow(L[1],x)=hipow(f,x) then
        (print(F,"irreductible"),
        return(false)),
     return(L)
);

LMod(t+x-1); LMod(ex);

### Remontée de Hensel Multifacteur à la précision k

MultiHensel(F,L,n) avec L une liste de polynomes (f1,...,fs) 
dont le produit vaut F modulo t renvoie la liste des fi relevés a la 
précision t^(2^n). 

On appelle Hensel(F,f1,f2*...*fr,n) pour relever f1, etc... 
 N.B : On peut faire beaucoup mieux via Bezout généralisé q1*f1+...+qr*fr=1...

MultiHensel(F,L,n):=block(
    [Liste,l,f,A,B,G,Hen],
    if n=0 then
        return(L),

    l:length(L),
    Liste:[],
    f:Mod(F,1),
    for i:1 thru l do
        (A:Mod(L[i],1),
         B:quotient(f,A),
         G:gcdex(A,B),
         Hen:Hensel(F,A,B,G[1],G[2],n),
         Liste:append(Liste,[Hen[1]])
        ),
   return(expand(Liste))
)$

### Remontée de Hensel Multifacteur à la précision t^(e+1), avec e=deg_t(F)

FactoModulaire(F):=block(
    [n,L,Liste],
    
    e:hipow(F,t),
    print("degré en t:", e),

    nn:entier(log(e+1)/log(2)),
    if nn= log(e+1)/log(2) then 
        n:nn 
    else n:nn+1,
    print("nombre d'itérations de Hensel requises:",n),
    
    L:LMod(F),
    print("Liste des facteurs modulo", t ," : ", L),
    L:MultiHensel(F,L,n),
    Liste:makelist(expand(Mod(L[i],e+1)),i,1,length(L)),
    return(Liste)
);

FM:FactoModulaire(ex);

Mod(ex-product(FM[i],i,1,length(FM)),9);

FMM:FactoModulaire(F1*F2);

Mod(F1-FMM[2]*FMM[3],4);

f:expand((x**2-t-1)*(x**3-t**2)*(x**2-2*t**3));

FactoModulaire(f);

## Exercice 4: La liste G1,...,Gs

ListeG(F,FM):=block(
    [e,l,Liste,dd,qq],
    e:hipow(F,t),
    l:length(FM),
    Liste:[],
    for i:1 thru l do
        (dd:diff(FM[i],x),
         qq:Mod(product(if j#i then FM[j] else 1,j,1,l),e+1),
         Liste:append(Liste,[expand(Mod(dd*qq,e+1))])),
    return(Liste)
);

Test 

FM:FactoModulaire(ex);

LG:ListeG(ex,FM);

sum(LG[i],i,1,4)-diff(ex2,x); 
expand(LG[2]+LG[3]-diff(F1,x)*F2);
expand(LG[1]+LG[4]-diff(F2,x)*F1);

fm:FactoModulaire(f);

LG2:ListeG(f,fm);

## Exercice 5: Recombinaisons

### On introduit l'opérateur D(G) du cours

Deriv(G,F):=block(
    [ft,fx,DG],
     ft:diff(F,t),fx:diff(F,x),
     DG:expand((diff(G,t)*fx-diff(G,x)*ft)*fx-(diff(fx,t)*fx-diff(fx,x)*ft)*G),
     return(DG)
);

### On fabrique le matrice de L et on calcule son noyau

Matrice(F,LG):=block(
    [s,DG,e,d,NbEq,M,L,c,i,j,k],
    
    s:length(LG),
    DG:makelist(Deriv(LG[i],F),i,1,s),
    e:hipow(F,t),
    d:hipow(F,x),
    NbEq:expand(e*(2*d-2)+3*e*d),
    print("Nombres d'équations:", NbEq),
    M:zeromatrix(NbEq,s),
    
    for i:1 thru s do
        (L:[],
         Q:expand(Mod(quotient(DG[i],F,x),3*e)),
         for j:2*e thru 3*e-1 do
            (c:expand(coeff(Q,t,j)),
             for k:0 thru 2*d-3 do
                L:append(L,[coeff(c,x,k)])
            ),
        R:Mod(remainder(DG[i],F,x),3*e), 
        for j:0 thru 3*e-1 do
            (c:coeff(expand(R),t,j),
             for k:0 thru d-1 do
                L:append(L,[coeff(expand(c),x,k)])
            ),
         for j:1 thru length(L) do
            M[j,i]:L[j]
         ),
    return(M)
);

Recombinaisons(F,LG):=block(
[M],
M:Matrice(F,LG),
return(nullspace(M))
);

LMod(ex);

R:args(Recombinaisons(f,LG2));

R[2][4][1];

## Exercice 6: L'algorithme de factorisation dans Q[t,x]

Enfin l'algorithme complet pour les polynomes unitaires réduit modulo t (avec test)

FactoBivariee(F):=block(
    [FM,LG,R,r,L,fac],
/*    if Test(F)=false then
        return(false),  */
    print("degré en x:",hipow(F,x)),
    FM:FactoModulaire(F),
    LG:ListeG(F,FM),
    R:args(Recombinaisons(F,LG)),
    r:length(R),
    if r=1 then 
        (print("Polynôme irréductible"),
        return([F])),
    L:[],
    for i:1 thru r do
        (fac:expand(Mod(product(if R[i][j][1]#0 then FM[j] else 1,j,1,length(FM)),hipow(F,t)+1)),
        L:append(L,[fac])),
    return(L)  
);

FactoBivariee(ex);

FactoBivariee(f);

EX:expand(ex*(x**6+t*3+x*t+1));

## Exercice 7: Inclusion de compteurs temps

timer(FactoModulaire,Recombinaisons,FactoAvecTemps);

FactoAvecTemps(F):=block(
    [FM,LG,R,r,L,fac,t1,t2,t3],

    t1:float(get(FactoModulaire,runtime)/100),
    t2:float(get(Recombinaisons,runtime)/100),
    t3:elapsed_run_time(),

    if Test(F)=false then
        return(false),
    print("degré en x:",hipow(F,x)),
    FM:FactoModulaire(F),
    LG:ListeG(F,FM),
    R:args(Recombinaisons(F,LG)),
    r:length(R),
    if r=1 then 
        (print("Polynôme irréductible"),
        return([F])),
    L:[],
    for i:1 thru r do
        (fac:expand(Mod(product(if R[i][j][1]#0 then FM[j] else 1,j,1,length(FM)),hipow(F,t)+1)),
        L:append(L,[fac])),

    print(""),
    print("Temps de la remontée de Hensel:", float(get(FactoModulaire,runtime)/100)-t1),
    print("Temps des recombinaisons:", float(get(Recombinaisons,runtime)/100)-t2),
    print("Temps total:", elapsed_run_time()-t3),
    print(""),

    return(L)  
);

stringout("FactoBiv.wxm",functions);