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 :
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.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])
Quelqu'un pourrait-il me confirmer ses informations et, si possible, me donner une piste d'implémentation ?
Merci par avance pour vos retours.
-----