Inscription / Connexion Nouveau Sujet
Algorithme(s) - Irréductiblité sur les corps finis.
Bonjour à tous, 
Position du problème: Je souhaite créer un programme (sous Maple) qui me permette de déterminer tous les polynômes irréductibles de degré k (fixé) su un corps fini (fixé au début lui aussi). En clair, on se donne un corps , un entier m et on cherche tous les polynômes irréductibles de
unitaires de degré m.
Bon, je suis encore loin de l'objectif fixé. 
J'ai commencé par écrire une procédure qui prend deux polynômes P1 et P2 comme paramètres et qui rend le quotient et le reste de la division euclidienne de P1 par P2. On dirait que je me suis viandé, mais je vois pas où... 
Voici ce que j'ai écrit:
euclide:=proc(P1,P2)
local Q:R:p:r:a:
Q := 0; R := P1; r := degree(R, x); p := degree(P2, x); a := coeff(P2, x^p)
while p < r or r = p do
Q := Q+coeff(R,x^r)*x^(r-p)/a:
R:= R-P2*coeff(R, x^r)*x^(r-p)/a:
r:= degree(R,x): od:
{Q,P};
end:
Tant que P2 est un monôme, pas de problème, il me retourne très rapidement le quotient et le reste. Par contre, dès que P2 n'est plus un monôme (par exemple x-1) j'ai l'impression qu'il boucle à l'infini, mais je vois pas où est le problème...
Quelqu'un peut-il m'aider pour résoudre ce problème? (Et même l'initial s'il le veut... 
).
Merci d'avance.
Ayoub.
Salut Ayoub
déjà, vaut mieux mettre des virgules entre les variables locales.
Ensuite, qu'est-ce que P ?
Enfin, pourquoi tu n'utilises pas rem et quo ?
Salut Guillaume,
P? Ou ça?
pourquoi tu n'utilises pas rem et quo ?
Euh, je vois disons, 2 bonnes raisons: Je savais pas que ça marchait pour les polynômes et ça me fait un bon entraînement pour les autres algo à programmer...
D'ailleurs je confirme: quo ne fonctionne pas avec des polynômes. Du moins, avec ma version de Maple, ça marche pas...
Au temps pour moi.
R n'est pas constant Guillaume puisqu'on le change à chaque itération...
Exemple:
euclide(2x²+3x+5,7x);
{5,2/7x+3/7}.
Oui je m'en suis rendu compte, j'avais touché à un truc
Et ba ça marche non ? j'ai le même résultat que toi, 2/7x+3/7
> restart;
> euclide:=proc(P1,P2) option remember:
local P,Q,R,p,r,a:
Q:=0:
R:=P1:
r:=degree(R,x):
p:=degree(P2,x):
a:=coeff(P2,x^p):
while p<=r do
Q:=Q+coeff(R,x^r)*x^(r-p)/a:
R:=expand( R-P2*coeff(R,x^r)*x^(r-p)/a):
r:=degree(R,x):
od:
Q,R:
end:
devrait marcher
J'ai identifié le blème, il fallait rajouter expand (développer) dans l'affectation de R.
R:=expand( R-P2*coeff(R,x^r)*x^(r-p)/a ):
renvoit un poly sous forme développée, maple peut ainsi faire des opérations dessus
Sinon, à titre informatif sous maple la ligne :
Factor((x^(p^k)-x)) mod p;
te donnera sans effort tous les polynômes irréductible de Z/pZ de degré divisant k.
algorithmiquement parlant la meilleur méthode pour les obtenir tous me semble quand même encore être de lister les éléments de Fp^(nm), es de les regrouper selon les orbites de l'action du morphisme de Frobenius x->x^(p^n) : chaque orbite possède e élément (avec e divisant m) et correspond aux racines d'un unique polynôme irréductible à coefficient dans Fp^n
Bonsoir Ksilver,
Oui, moi aussi, je voulais utiliser le critère d'irréductibilité de Rabin. Dans le cas k=Fp faire comme tu le fais me semble effectivement la bonne méthode.
Mais dans le cas quelconque (caractéristique p mais cardinal de la forme p^n) ça se complique vraiment. Je sais pas trop comment Maple fonctionne avec les corps finis quelconques.
Annuler
connectez vous
algèbre en post-bac