Algorithme de Berlekamp

[barbu23]

Bonsoir à tous : :happy3:
J'ai un peu de mal à comprendre à quoi sert l'algorithme de Berlekamp dans la factorisation de polynomes dans un corps fini ! On dit qu'il est surtout conçu pour factoriser des polynomes de type : , mais d'après, cet article suivant que je viens de lire en coup de vent : http://fr.wikipedia.org/wiki/Algorithme_de_Berlekamp , j'ai du mal à mettre en lien, cette algorithme, et la factorisation d'un polynome quelconque dans !
Est ce que vous connaissez un exemple d'application concrète à ce théorème ?
Par exemple :
On se donne : .
Factoriser à l'aide de l'algorithme de Berlekamp.
Merci d'avance !

[Joker62]

Moi je connais une utilisation de cet algorithme pour montrer que X^p - X - 1 est irréductible dans Fp !

Mais ça se fait aussi facilement à la main donc bon, un intérêt ? Peut-être en numérique je ne sais pas.

[Joker62]

Et avant de me demander de te le montrer et sachant que tu aimes bouquiner, je te renvois au livre Beck Malick Peyré : Objectif Agreg.

[wserdx]

Oui, l'intérêt de cet algorithme est avant tout numérique. C'est à dire qu'il sert à factoriser des polynômes quelconques, mais dont les coefficients sont numériquement connus.

[barbu23]

Ok ! par exemple, celui là :

[Ben314]

Pour quel p premier ?

[barbu23]

doit être necessairement premier ? :hum:
Par exemple :

[Ben314]

Modulo 7 :
4 n'est pas vraiment premier... (et sur un anneau non intègre, je sais pas trop quel peut être l'intêret de factoriser...)

[barbu23]

Modulo 7 :
4 n'est pas vraiment premier... (et sur un anneau non intègre, je sais pas trop quel peut être l'intêret de factoriser...)

Oui, mais Ben314, comment tu fais pour trouver le resultat, c'est ça ce qui est important ! :hum: :happy3:

[Ben314]

Je vais être honnête : j'ai tapé
"Factor(X^6+X^4-1) mod 7" sous Maple...
Je sais que des algo. plus ou moins efficaces sont implémentés sous Maple, mais je sais pas si c'est exactement celui là...

Si tu y tient, essaye de voir pas à pas comment fonctionne l'algo sur cet exemple, moi j'ai franchement la flemme.... :dodo:

[barbu23]

lol ! :king:

[Joker62]

Le P ne doit pas avoir de facteurs carrés non plus...(C'est une remarque pas un reproche sur l'exemple précédent)

Et donc vu l'algorithme.. Un calcul de noyau de rang et tout le bazar c'est quand même chiant... Autant savoir que ça existe et s'arrêter là...

[Ben314]

Le P ne doit pas avoir de facteurs carrés non plus

O.K., mais les facteurs carrés, c'est façile à repérer : tu calcule P' puis s'il n'est pas identiquement nul, le pgcd(P,P') : ca te donne les éventuels facteurs carrés.
Si P' est identiquement nul alors tu as immédiatement une grosse indic. sur la factorisation de P (je laisse chercher ceux qui connaissent pas la réponse...)

[barbu23]

Bonsoir : :happy3:
J'avoue, j'ai lu cet article de wikipedia que j'ai posé au debut de ce fil, mais je n'arrive pas encore, à trouver un lien entre ce qui se dit sur ce lien, et la factorisation de polynomes dans les corps fini ! :hum:
Bref, je viens, de trouver cet article qui est plus lisible concernant l'algorithme de Berlkamp , est ce que c'est la même chose que ce qu'il y'a sur wikipedia ?
http://www.math.univ-toulouse.fr/~couveig/berlekamp89.pdf
Après, j'entamerai dans l'application de cette algorithme ! :happy3:
Merci de votre aide ! :happy3:

[Ben314]

J'ai l'impression que c'est bien la même chose...

[barbu23]

Ben314, tu regardes biensûr la page ! Ok ! Je fais passer au travail maintenant ! :happy3:

[barbu23]

Ben314 :
Je pose :
Ensuite, je calcule :

Ensuite, c'est quoi : ?
Merci d'avance ! :happy3:

[barbu23]

svp, faites l'application à ma place ! :happy3:

[Ben314]

Tu utilise l'algo d'euclide (divisions successives) pour le trouver (si tu veut "faire à fond comme l'algorithme").

[barbu23]

J'arrive pas à faire ce travail seul ! sincèrement ! :triste: