Algorithme d'Euclide étendu

Soyez le premier à donner votre avis sur cette source.

Vue 6 960 fois - Téléchargée 807 fois

Cette source est considérée comme dangereuse, elle a néamoins été gardée dans un but pédagogique :

Télécharger le projet
Commenter

Description

Bonjour chers utilateurs de CodeS-SourceS,

Je vous propose un petit code Python de calcul concernant l'algorithme d'Euclide étendu :
(Merci à qui a rédigé la page web :
url{http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu}) dont j'ai
appliqué l'algorithme et dont je reprends le texte de début
(voir pdf joint en plus digeste) :
L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet,
à partir de deux entiers a et b, de calculer non seulement leur plus grand commun
diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout
(deux entiers u et v tels que au + bv = PGCD(a, b)).
Quand a et b sont premiers entre eux, u est alors l'inverse pour la
multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b,
modulo a), ce qui est un cas particulièrement utile.
L'algorithme d'Euclide étendu fournit également une méthode efficace non
seulement pour déterminer quand une équation diophantienne ax+by = c
possède une solution, ce que permet déjà l'algorithme d'Euclide simple,
mais également pour en calculer dans ce cas une solution particulière,
dont on déduit facilement la solution générale.

Bonne journée ou bonne soirée,

hbouia
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
hbouia
Messages postés
107
Date d'inscription
mardi 30 juillet 2013
Statut
Membre
Dernière intervention
17 avril 2019
 5 -
Bonjour et merci pour vos remarques et suggestions,
L'idée était juste de retranscrire l'algorithme d'Euclide étendu tel quel et qui est valable pour les très grands nombres entiers et non seulement dédié à des calculs manuels de coin de table.
Il est très utilisé par exemple en cryptographie par exemple en chiffrement RSA entre autres.
Cordialement,
hb
Signaler
zimou130
Messages postés
3
Date d'inscription
vendredi 23 février 2018
Statut
Membre
Dernière intervention
24 février 2018
 -
Pour de tels exercices il serait préférable d'appliquer le "SCHEMA D'OURAGH" qui est une synthètisation de l'algorithme étendu. Vous pouvez juger par vous même que la solution de l'exemple que vous résolvez se réduit au simple tableau à trois lignes suivantes
164 72 20 12 8 4
-2 -3 -1 -1
(16) (-7) 2 -1 1
tableau très facile à remplir..

***Modération CCM
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (hbouia)