Bézout Modulaire
Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

Bézout Modulaire



  1. #1
    inviteb6caabbc

    Bézout Modulaire


    ------

    Bonjour à tous

    Alors voila j'ai un exercice à faire mais je ne comprends strictement rien. Merci à vous si vous pouviez me donner des indications.
    J'ai bien réussi la 1ère question mais pour le reste, je ne vois pas du tout quoi faire.

    Enoncé:


    Soit A et B deux polynômes à coefficients entiers et premiers entre eux. Soit c ∈ ℤ* le résultant de A et B, on va calculer les polynômes U et V de l’identité de Bézout
    A U + B V = c , deg(U)<deg(B), deg(V)<deg(A) (9)

    par une méthode modulaire.

    1. Montrer, en utilisant les formules de Cramer, que les coefficients de U et V sont des entiers de valeur absolue inférieure ou égale à la borne de Hadamard h de la matrice de Sylvester de A et B (dont le déterminant est c, le résultant de A et B). Calculer h en fonction de la norme euclidienne de A, B et de leurs degrés.

    2. On calcule c ∈ ℤ* puis on résoud (9) dans ℤ/pi Z[X] pour plusieurs nombres premiers pi (choisis si possible inférieurs à √(2^31) pour des raisons d’efficacité), puis on calcule par le théorème des restes chinois (9) dans ℤ/∏pi Z[X]. Donner une minoration de ∏i pi faisant intervenir h qui permette de garantir que l’écriture en représentation symétrique de (9) dans ℤ/∏pi Z[X] est identique à (9) dans ℤ[X].

    3. Application : résoudre de cette manière l’équation de Bézout pour
    A=(X+1)^4(X−3), B=(X−1)^4(X+2)
    (vous pouvez utiliser sans justifications l’instruction de calcul de résultant, des coefficients de Bézout dans ℤ/piZ[X] et de reste chinois de votre logiciel).

    4. Écrire une fonction mettant en oeuvre cet algorithme.

    5. Que pensez-vous de l’intérêt de cet algorithme par rapport à l’algorithme d’Euclide étendu dans ℤ[X]?



    Merci beaucoup

    -----

  2. #2
    inviteb6caabbc

    Re : Bézout Modulaire

    J'ai beau tourner le théorème des restes chinois dans tous les sens je ne vois pas comment commencer et encore moins comment je vais introduire h.

    Théorème des restes chinois:

    Si m1, ..., mn sont des entiers supérieurs à 2 deux-à-deux premiers entre eux, alors, pour des entiers a1, ..., an, le système d'équations:

    x mod m1 = a1
    ...
    x mod mn = an

    admet une unique solution modulo M = m1 · ... · mn donnée par la formule:

    x = (a1M1y1 + ... + anMnyn) mod M

    où Mi = M/mi et yi = Mi-1 mod mi pour 1 i n.


    Merci

    En fait je me demande à quoi l'on veut arriver étant donné qu'avec les formules de Cramer on peut répondre au problème.

Discussions similaires

  1. forme modulaire
    Par invite7cf6f611 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 07/11/2008, 14h13
  2. [Thermique] horloge modulaire
    Par invitef4491fcc dans le forum Dépannage
    Réponses: 1
    Dernier message: 08/05/2008, 15h40
  3. Exponentiation modulaire
    Par invite13a949b5 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 28/01/2008, 17h44
  4. Puissance Modulaire
    Par invite13a949b5 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 29/12/2007, 22h28
  5. Arithmètique Modulaire
    Par invite0d212215 dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 27/12/2007, 21h37