# TP 2 : Factorisation dans Z[Y]

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

### EtapeHensel : de mod p à mod p^2

Si F=gh mod p et gs+tv=1 mod  p, avec h monique , deg(g)+deg(h)=deg(f) et deg(s)<deg(h), deg(t)< deg(g),

EtapeHensel renvoie une liste [gg,hh,ss,tt] avec F=gg * hh mod p^2 et gg*ss+hh*tt=1 mod (p^2) 

et avec hh monique , deg(gg)+deg(hh)=deg(f) et deg(ss)<deg(hh), deg(tt)< deg(gg) 

EtapeHensel(F,g,h,s,t,p) := block(
    [e,l,gg,hh,d,ss,tt],
    modulus:p**2,
    e : polymod(F-g*h),
    q: polymod(quotient(s*e,h)),
    r: polymod(remainder(s*e,h)),
    gg : polymod(g + t*e+q*g),
    hh : polymod(h + r),
    d : polymod(t*hh+s*gg-1),
    qq: polymod(quotient(s*d,hh)),
    rr: polymod(remainder(s*d,hh)),
    ss : polymod(s-rr),
    tt : polymod(t-t*d-qq*gg),
    modulus:false,
    return ([gg,hh,ss,tt]) 
)$

functions;

### Hensel : en itérant EtapeHensel, on lifte modulo p^(2^k).

En itérant EtapeHensel, on lifte modulo p^(2^k).

Hensel(F,g,h,s,t,p,k) := block(
    [l],
    if k=0 then
        return([g,h,s,t]),
    modulus:p,
    if polymod(F-h*g) # 0 then 
        (print ("mauvaise factorisation mod ", p),
        return ()),
    if polymod(gcd(polymod(h),polymod(g))) # 1 then 
        (print ("facteurs mod ", p , "non premiers entre eux"),
        return ()),
    if polymod(s*g+t*h,p) # 1 then 
        (print ("mauvaise identité de bezout"),
        return ()),
    l:EtapeHensel(F,g,h,s,t,p),
    for i:1 thru k-1 do
        (p:p**2,
        l:EtapeHensel(F,l[1],l[2],l[3],l[4],p)),
    modulus:false,
    return (l)
)$

functions;

### Tests

(p:3, k:3,
H:x**5-61*x**4+58*x**3+83*x**2-45*x+26, 
G:x**3-82*x**2+525*x-91,
F:expand(H*G),
modulus : p,
h:polymod(H),
g:polymod(G),
s:gcdex(g,h)[1],
t:gcdex(g,h)[2]
)$

EtapeHensel(F,g,h,s,t,p);

l:Hensel(F,g,h,s,t,p,k);

modulus:false;

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

polymod(F-l[1]*l[2],p^(2^k));

functions;

## Exercice 2 : factorisation de F modulo p^(2^k)

### Liste des facteurs de F modulo p

On retourne d'abord la liste des facteurs de F modulo p (qui renvoie faux si F non réduit mod p)

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

### Liste des facteurs de F modulo p^(2^k)

%  On définit ensuite MultiHensel(F,L,p,k) avec L une liste de polynomes (F1,...,Fr) dont le produit vaut F modulo p. 
%  Cette fonction renvoie la liste des Fi relevés a la précision modulo p^(2^k). 
%  On appelle Hensel(F,F1,F2*...*Fr,p,k) pour relever F1, etc... 
%
%  N.B : On peut faire mieux en utilisant des relations de Bezout généralisées...Q1F1+...+QrFr=1, mais bon...

MultiHensel(F,L,p,k):=block(
    [l,A,B,U,V,H],
    if k=0 then
        return(L),
print("Liste facteurs modulo", p ," : ", L),
    l:length(L),
    Liste:[],
    modulus:p,
    f:polymod(F),
    for i:1 thru l do
        (modulus:p,
        A:polymod(L[i]),
print("A=",A),
        B:polymod(quotient(f,A)),
print("B=", B),
        U:gcdex(A,B)[1],
print("U=", U),
        V:gcdex(A,B)[2],
print("V=", V),
        H:Hensel(F,A,B,U,V,p,k),
print(polymod(expand(F-H[1]*H[2]),p**k)),
        Liste:append(Liste,[H[1]]),
print(Liste)
        ),
   return(Liste)
)$

% Test

F;

L:LMod(F,3);

MF:MultiHensel(F,L,3,4);

polymod(F-product(MF[i],i,1,length(MF)),3**(2**4));

% Finalement on peut définir la fonction FactoModulaire(F,p,k) en combinant les deux fonctions précédantes

FactoModulaire(F,p,k):=block(
    return(MultiHensel(F,LMod(F,p),p,k))
);

## Exercice 3 : précision du lifting

% Calcul de la borne de Landau-Mignotte sur la norme des coefficients d'un facteur de F dans Z[x]

Mign(F):=block (
    [S],
    d:hipow(F,x),
    S : sum(coeff(F,x,i)^2,i,0,d),
    return (binomial(d,entier(d/2))*sqrt(S))
);

Mign(F);

% Calcul de la précision de la remontée de Hensel.

Precision(F,p):=block (
    [n],
    n:log(Mign(F))/log(p),
    return(entier(log(n)/log(2))+1)
);

Precision(F,3);

## Exercice 4 : recombinaisons des facteurs modulaires

### Partitions triées de la liste des facteurs modulaires

% On définit un ordre de manière à ce que chaque facteur trouvé soit automatiquement irréductible

Inf(L1,L2):=block(
    if length(L1[1]) <= length(L2[1]) then
        return (true));

% On introduit une fonction partition triée  : Partition(3) retourne P=[[{1},{2,3}],[{1,2},{3}],[{1,3},{2}]]
% Le tri est fait selon un semi-ordre ordre Inf que l'on crée de maniere a ce que le premier facteur trouvé correspondant à P[i][1] soit forcément irréductible.
% On pourrait de manière équivalente parcourir des combinaisons de k parmis n avec k de 1 à n/2, mais bon...

Partition(n):=block(
    Indices:makelist(i,i,1,n),
    S:listify(set_partitions(setify(Indices),2)),
    return(sort(makelist(listify(S[i]),i,1,length(S)),Inf))
);

Partition(5);

### Recombinaisons

% On introduit une fonction récursive Recombinaisons(F,H,P,p) : F est un polynome unitaire reduit de Z[x]
%                                                               H est une famille de polynomes tels que F=prod H[i] et H[i] divise F mod (p^k) pour k=Precision(F,p)
%                                                               P est un ensemble de partitions des indices de H. 
% La fonction retourne la liste des combinaisons des H[i] qui sont facteurs irréductibles de F.   

Recombinaisons(F,H,P,p):=block(
       if coeff(F,hipow(F,x))=1 or length(H)<= 1 or length(P)=0 then
            return([F]),
print("NOUVELLE BOUCLE : partitions à parcourir = ", P), 
       modulus:false,   
       prec:Precision(F,p),
       m:p**(2**prec),
print("Precision = ", m),
       A:1,
       for k in P[1][1] do
            A:polymod(expand(A*H[k]),m),
print("A=",A),
       if remainder(F,A)=0 then 
            (
print("A est facteur irreductible"),
             B:quotient(F,A),
             HH:H,
             for k in P[1][1] do 
                    HH:delete(H[k],HH),
             P:Partition(length(HH)),
print("nouveau triplet (F,H,P)= ", B , HH, P),
             return(append([A],Recombinaisons(B,HH,P,p)))
            )
       else
            (
            P:delete(P[1],P),
print("A n'est pas facteur"),
            return(Recombinaisons(F,H,P,p))
            )
);

MF;

P:Partition(length(MF));

factor(F);

Recombinaisons(F,MF,P,3);

## Exercice 5 : Factorisation des polynômes dans Z[X] séparables unitaires

### Test si unitaire réduit sur Z

TestZ(F):=block(
    if coeff(F,x,hipow(F,x)) # 1 then 
        (print ("F non unitaire"),
        return(false))
    elseif resultant(F,diff(F,x),x)=0 then
        (print ("F non séparable sur Z"),
        return(false))
    else 
        return (true)
);

### Trouve le premier p plus grand que n tq F unitaire réduit mod p

TrouveP(F,n):=block(
    [p,f,R],
    p:next_prime(n),
    modulus:p,    
    f:polymod(F,p),
    R:resultant(f,diff(f,x),x),
    if R=0 then
        (print("F non séparable modulo", p),
         TrouveP(F,p))
    else
        (print("Le premier bon premier superieur strict à n est p = ",p),
        return(p))
);

TrouveP(x**2-30,4);

### Factorisation des polynomes unitaires réduit (avec test)

FactoUnitaire(F):=block(
     if TestZ(F)=false then
            return(false),
     p:TrouveP(F,1),
     modulus:false,
     L:LMod(F,p),
     if L=false then 
            return([F]),
     print("Liste facteurs modulo ", p, " : ", L),
     prec:Precision(F,p),
     print ("precision de la remontée de Hensel :", prec, " itérations"),
     H:MultiHensel(F,L,p,prec),
print(H),
     if H=false then 
            return([F]),
     P:Partition(length(H)),
     return(Recombinaisons(F,H,P,p))
);

### Tests, avec affichage de temps

showtime : true;

FactoUnitaire(F);

FactoUnitaire(x**2-1);

Test1:expand((x**3-27)*(x**2-4));

FactoUnitaire(Test1);

(F1:x**4-3*x**3+7*x**2-x+5,F2:x**3-5*x**2+6*x-4,F3:x**6+5*x-1,F4:x**3-1,Test2:expand(F1*F2*F3*F4));

FactoUnitaire(Test2);

## Exercice 6 : Algorithme complet de factorisation sur Z[x]

### Réduction au cas séparable

### Réduction au cas unitaire

### L'algorithme complet 

% Factorisation(F) retourne [c,(F1,m1)...,(Fr,mr)], liste des (facteurs, multiplicités) de F sur Z.

## Exercice 7 : Variantes...

% Par exemples, tests de recombinaisons pour des précisions plus petites que celles imposées par Landau-Mignotte.  

## Exercice 8 : Tests de complexité

### Inclure des compteurs temps dans les sous-procédures de Factorisation(F) 

### Créer un tableau (d, p, NbFacModp, NbFac, temps du lifting, temps des recombinaisons)

### Créer une liste de n polynômes aléatoires pour des paramètres (d,p,NbFacModp,NbFac) fixés

### Remplir le tableau pour F parcourant les listes 

### Tracer des courbes TempsTotal en fonction des différents paramètres.