Langage Formel - Factorisation de polynômes multivariés - Page 1

Bonjour,

Je suis en Master1 d'informatique et j'ai écopé d'un sujet qui, à mon grand damn, me frappe sur une faiblesse d'assez longue date : les mathématiques ...

Je m'explique : Je dois réaliser un programme qui factorise (si possible) dans Z/pZ un polynôme (univarié ou multivarié) de degré n.

Les recherches que j'ai effectué m'ont permis d'aboutir à deux méthodes :

Cantor - Zassenhaus, qui utilise des corps, des anneaux et d'autres trucs auxquels je ne comprends rien :/

Berlekamp, qui utilise de l'algèbre linéaire, certes un peu plus facile à cerner, mais dont l'application pour cet exercice me plonge dans le désespoir le plus total.

Je poste ce topic, non pas pour y trouver une super méthode magique, mais dans l'espoir que l'un d'entre vous connaisse un lien, une réference, un article quelconque, n'importe quoi, qui pourrait faire usage d'un minimum de vulgarisation dans l'explication de tels concepts.

Merci de m'avoir lu

PS : ce projet m'a fait apprendre un nouveau mot hier : Abscons

Télécharge les polys « Cours d'algèbre 1 fait à l'E.N.S. (première année du M.M.F.A.I.) en 2003-2004 et 2004-2005 » sur http://www.math.u-psud.fr/~harari/enseignement/

tu y trouveras tout ce dont tu auras besoin pour comprendre les corps, les anneaux et même plus.

Ok merci, j'espère y comprendre quelquechose cette fois ci

Me re-voilà

Je suis toujours sur mon projet de factorisation et j'ai un nouveau problème :

J'ai une fonction qui me calcule la division euclidienne de deux polynomes, et je souhaiterais adapter cette fonction pour qu'elle fasse des divisions entre polynomes "modulés".

La version actuelle de la division multiplie le dividende par un nombre donné () assurant que tous les coefficients durant l'opération restent entiers.

Mais, les résultats obtenu pas cette fonctions en appliquant un modulo ne correspondent pas avec ceux de GIAC (ou autre logiciel de calcul formel) :

Exemple :
En modulo 5 :

/

==> Je trouve (ce qui correspond à 5x^2 -11x -1 sans le modulo)

==> GIAC trouve : .

Je pense que j'ai faux car la méthode du multiplicateur du dividende de fonctionne pas dans ce cas, mais je n'en suis pas sûr ...

J'en appelle donc à votre savoir pour m'éclairer sur la marche à suivre,

Merci

Je sais pas exactement par quoi tu multiplies (coefficient dominant du diviseur [=2] puissance différence des degrés plus 1 [=3] ? [=8]), mais dans tous les cas si tu fais ça dans Q[X] tu devrais trouver (et évidemment si tu fais ça dans Z[X] tu devrais trouver 8x ça)

EDIT : Exact, j'ai une feuille remplie de divisions de polynomes alors j'ai du recopier un autre truc, car effectivement, je ne trouve pas mais bien

-----

Je sais pas exactement par quoi tu multiplies (coefficient dominant du diviseur [=2] puissance différence des degrés plus 1 [=3] ? [=8])

Oui, c'est ce que je fais, mais une pause d'une soirée m'a permis de trouver une possibilité qui me semble correcte (mais pas avec certitude) :

Je ne multiplie pas le dividende, mais je cherche plutôt un produit dont la valeur modulo M est égale au coefficient dominant du dividende :



Je cherche p tel que 2p = 1 % 5 ; pour p = 3, 2*3 congru à 1 mod 5

J'ajoute donc à mon quotient,

reste (1) :



Je re-cherche un p tq 2p = 3 % 5 ; p = 4, le quotient passe donc à

reste (2) :

Je recommence encore à chercher une valeur pour p (2p = 1%5 donc je choisi p = 3), ce qui complete mon quotient à

reste (3) :

alleluia

Je pense tenir là l'astuce néanmoins je n'en suis pas certain. Aussi aimerais-je avoir votre avis

Au cas où cette méthode s'avererait être correcte, je doit donc trouver mon "p" de tout à l'heure et donc j'ai la relation suivante :

Pour :
d = coefficient dominant du dividende,
q = coefficient dominant du diviseur,
M = valeur de mon modulo,

q * p congru à d mod M

Connaissez-vous un méthode pour connaître une valeur de p (si possible sans itérations successives) ?

Il faut que tu utilises Euclide étendu pour trouver un inverse q' de q modulo M (seulement si gcd(q,M) = 1) et alors p=dq', et ça se fait en O(log(q)log(M))

http://en.wikipedia.org/wiki/Extended_euclidean_algorithm

Hello, merci pour vos réponses

J'ai résolu mon problème pour trouver p avec une méthode "à l'arrache" en testant une à une toutes les valeurs du modulo (c'est bourrin mais ça marche à tous les coups étant donné que je suis en modulo un nombre premier)

Mais me revoilà pour un nouveau problème (enfin pas tout à fait) :

Je dois utiliser une identité de Bezout généralisée pour générer un certain nombre de polynomes :

J'ai la formule suivante :

Rn, Pn, Qn, Pk et Q sont des polynomes sachant que pgcd(produit_des_Pk, Pn)=1.

Je cherche Rn et Qn.

Le truc c'est qu'il me semble que cette formule fait référence à au+bv=pgcd(a,b), or ici le Pn et le produit des Pk sont premiers entre eux. Et bien évidemment Q est lui bien différent de 1 :/


J'ai lu également sur un site qui traite du sujet (Arithmétique des polynomes qu'on pouvait avoir au+bv=c mais seulement si c est divisible par pgcd(a,b), et dans ce cas, on a : acu+bcv=c*pgcd(a,b). mais vu que le pgcd=1, celà revient à au+bv=1.

Je ne pense pas m'être trompé car wikipédia m'indique bien sur cette page que pour tout a,b,d dans Z, il existe x,y tq ax+by=d.

Auriez vous un complément de démonstration ou un exemple de calcul (même sur des entiers, peu importe) ?

PS : La méthode que je tente d'implémenter est expliquée (un peu rapidement pour moi) sur un document rédigé par B.Parisse, trouvé sur son site http://www-fourier.ujf-grenoble.fr/~parisse/cas/fact.ps ( je l'ai aussi mis en pdf sur mon ftp : factorisation.pdf)

Si vous souhaitez jeter un coup d'oeil, c'est tout à la fin

En espérant ne pas trop abuser

trouves r'n et q'n tel que r'n * pn + qn * pi(pk) = 1 (possible car gcd(pn, pi(pk)) = 1)
alors (r'n * q) * pn + (qn * q) * pi(pk) = q

Ah mais oui, évidemment, en plus, je l'ai vu cet exemple, mais visiblement je devais bien fatigué quand je l'ai lu

Merci bien dualmoo

bonjour,

il faut factoriser

a= 3 t(puissance2 - 27=
j'ai mis 3(tpuissance2 - 9)

b= xpuissance3 + 2 xpuissance2 + xypuissance2=
j'ai mis, x(xpuissance2 + xy + ypuissance2)

c= xpuissance3 - 2 xpuissance2 - 16 x +32 = ?

d= 36 xpuissance2 y + 4 xpuissance2 ypuissance2 - 24 xpuissance2 ypuissance2
e= (3x - 5) (x + 4) ( + 9 xpuissance2 - 25
f= (xpuissance2 + 4) ( x - 2) - (x - 2) (2 x + 2) - 2 (x - 1) (x -2)


il faut factoriser, puis les mettre sur facteurs remarquables

g= (xpuissance2 + 4 xy + 4 ypuissance2)(xpuissance2 - 4 xy + 4 ypuissance2)
h= (x + 1)(x+ 2) - (x +2 ) (x -3)+ (x + 4)(x -3) - (x + 4)(x-1)


réduire au même dénominateur


i= ________7_______ j= ______3_________
apuissance 2 -4 2a - 4


k=____________1_________ l= ________3__________
xpuissance2+ 4x + 4 xpuissance2 + 2x




effectuer


r) (1- __x_=(1 + _x_)
a a

s= _5a - 10 ab_________ : ___25 ax - 50bx_____________
a + 2 a puissance2 + 2a


t = (_____1__ + _____1___ +______1__) x ____9 xpuissance2 - 1_______
3x - 1 x 3x + 1 4x

merci de votre aide

titie, tu peux utiliser , ça sera plus lisible

merci je vais essayer d'utiliser pretty print
à plus