Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige examen14 1 Cryptographie et arithmétique Corrigé d ? examen Université de Bordeaux Cryptographie et arithmétique ?? Corrigé de l ? examen Exercice Si x ?? y mod N et x ?? y mod N alors N ne divise pas x y mais divise x ?? y x ?? y x y La première

Cryptographie et arithmétique Corrigé d ? examen Université de Bordeaux Cryptographie et arithmétique ?? Corrigé de l ? examen Exercice Si x ?? y mod N et x ?? y mod N alors N ne divise pas x y mais divise x ?? y x ?? y x y La première condition de congruence implique donc que pgcd N x y N et la seconde que pgcd N x y si p est un diviseur premier de N alors par le lemme d ? Euclide il divise x ?? y ou x y le pgcd de N et x y est donc un diviseur non trivial de N On peut résoudre ceci de manière systématique sans faire des essais au hasard Je prends le temps de détailler la méthode mais cela n ? est pas nécessaire d ? en faire autant dans la rédaction voir les corrections en TD On cherche à obtenir une congruence du type x ?? y mod N en prenant pour x un produit de certains nombres du membre de gauche le membre de droite est alors un carré noté y si ?? et les nombres premiers apparaissant dans le membre de droite dont on s ? est débrouillé pour qu ? ils soient dans B une fois le produit formé sont tous à une puissance paire Mathématiquement ceci revient à trouver des entiers dans tels que dans ?? toutes les puissances soient paires i si le i-ième nombre de notre colonne ne ?gure pas dans le produit et sinon Ceci revient donc à résoudre le système suivant modulo donc dans Z Z F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F On peut encore le simpli ?er un peu avant de le résoudre puisqu ? on voit immédiatement que et donc que et ne ?gureront pas dans le produit x F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F On en arrive facilement à le reste étant nul Donc est une solution ce qui signi ?e que x fournit une solution à notre problème il est bien sûr plus commode de plutôt prendre x ?? mod On a dans ce cas y et pgcd N x ?? y pgcd N x y calculés gr? ce à l ? algorithme d ? Euclide étendu qui sont deux diviseurs non triviaux de N en vérité ce sont deux diviseurs premiers et ce sont les seuls CCryptographie et arithmétique Corrigé d ? examen Université de Bordeaux Exercice Notons d ? abord que c ?? me mod N par dé ?nition et donc c ?? me mod p et mod q Montrons que