Bonjour,

Je me permets de poster ici, ne sachant pas trop quoi faire pour implémenter l'algo F4.

J'ai commencé par coder quelques fonctions qui me seront utiles :

Code:
var='x'
n=3
Field=GF(3)
Z=PolynomialRing(Field, var, n, order='degrevlex') #Anneau de polynôme à n variables avec l'ordre degrevlex
Z.inject_variables()

# Fait la liste des monomes de degré m fixé
def monome(m):
    if m==0 :
        Monome=[1]
    else :
        Monome=[Z({tuple(a):1}) for a in WeightedIntegerVectors(m,[1 for i in range(0,n)])]
    return Monome

# Fait la liste des monomes de degré plus petit que m fixé
def monome2(m):
    Monome2=[]
    for i in range(0,m+1):
        Monome2=Monome2+monome(i)
    return Monome2

# Donne les tous les monomes qu'on trouve dans le système S sans les doubons. 
def monome_sys(S):
    U=[]
    U2=[]
    for f in S:
        U=U+f.monomials()
    for element in U : #sert à enlever les doublons de la liste
        if element not in U2:
            U2.append(element)
    U2.sort()
    return U2

# Calcul le degré max du système S
def degre(S):
    n=len(S)
    L=[]
    for i in range(0,n):
        L=L+[S[i].degree()]
    return max(L)

# Fonction qui décrit les équations de corps (renvoie une liste avec les équations de corps)
def Fieldeq():
    p=(Field.prime_subfield()).cardinality()
    Feq=[]
    for i in range(0,n):
        Feq=Feq+[Z.gen(i)^p-Z.gen(i)]
    return Feq

#On rentre une liste de poly L et il nous ressort cette liste de poly en enlevant
# les puissances de la caractèrisque du corps où on est.
def SansEqCorps(L):
    L2=[]
    Eq=Fieldeq()
    for i in range(0, len(L)):
        l=L[i]
        for j in range(0, len(Eq)) :
            l=l%(Eq[j])
        L2=L2+[l]
    #L3=[]  # on va enlever des doublons s'il y en a eu
    #for element in L2 : #sert à enlever les doublons de la liste
        #if element not in L3:
            #L3.append(element)
    return L2

# fait la matrice de Macaulay du système (on va y ajouter le fait qu'on veut le système soit sans carré)
def Macaulay(S,d):
    l=degre(S)
    M=monome2(d-l) # on fait la liste des monomes que l'on veut utiliser dans la multiplication
    U = [] # liste où ranger les produit des poly de S avec les monomes de S
    for i in range(0, len(S)):
        for j in range(0, len(M)) :
            U=U+[S[i]*M[j]]
    U=SansEqCorps(U)
    MSys=monome_sys(U)
    MatrixMacaulay=matrix(Field, len(U), len(MSys) , lambda x,y : 0 ) #on initialise la matrice à 0
    for x in range(0, len(U)):
        for y in range(0, len(MSys)):
            if MSys[y]==Z(1):
                a=U[x](tuple([0]*n))
            else :
                a=U[x].coefficient(MSys[y])
                a=a.constant_coefficient()
            if a in Field : # on rajoute une étape pour vérifier si on a bien un coeff constant (sinon c'est qu'on vient d'un autre monome)
                MatrixMacaulay[x,y]=a
    return MatrixMacaulay

# Modification de Macaulay pour qu'il ne retourne pas que la matrice de Macaulay mais aussi 
#les monomes qui aparaissent dans le système
def Macaulay2(S,d):
    l=degre(S)
    M=monome2(d-l)
    U = [] # liste où ranger les produit des poly de S avec les monomes de S
    for i in range(0, len(S)):
        for j in range(0, len(M)) :
            U=U+[S[i]*M[j]]
    U=SansEqCorps(U)
    MSys=monome_sys(U)
    MatrixMacaulay=matrix(Field, len(U), len(MSys) , lambda x,y : 0 )
    for x in range(0, len(U)):
        for y in range(0, len(MSys)):
            if MSys[y]==Z(1):
                a=U[x](tuple([0]*n))
            else :
                a=U[x].coefficient(MSys[y])
                a=a.constant_coefficient()
            if a in Field : # on rajoute une étape pour vérifier si on a bien un coeff constant (sinon c'est qu'on vient d'un autre monome)
                MatrixMacaulay[x,y]=a
    return MatrixMacaulay, MSys

#On doit rentrer des systèmes où la dimension du noyau de la matrice de Macaulay arrive à 1 sous peine de faire une boucle infinie
borne=10 # on se fixe une borne pour ne pas avoir de calculs infinis
def assignation(S): 
    l=degre(S)
    d=l
    while  ( (Macaulay(S,d).right_kernel()).dimension()!=1 and (Macaulay(S,d).right_kernel()).dimension()!=0)  and d<borne :
        d=d+1
    if d==borne:
        print('La dimension du noyau n\'est pas 1. Voici une assignation possible')
    if (Macaulay(S,d).right_kernel()).dimension()==0 :
        print('La dimension du noyau de la matrice est 0 pour d =', d)
    else :
        Mac, MSys = Macaulay2(S,d)
        Noyau =Mac.right_kernel()[1]
        print('d=', d)
        for i in range(0, len(MSys)):
            print(MSys[i], '=', Noyau[i])
Si j'ai bien compris, il faut que j'écrive une fonction de sélection qui renvoie un sous-ensemble de P non vide et une fonction de réduction qui renvoie un ensemble de nouveaux éléments formant une base à partir de P' (retour de la fonction de sélection) et de la base actuel G.

Quelqu'un pourrait-il me confirmer ses informations et, si possible, me donner une piste d'implémentation ?

Merci par avance pour vos retours.