Algorithme d'Euclide étendu
Soyez le premier à donner votre avis sur cette source.
Vue 8 384 fois - Téléchargée 1 000 fois
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
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
Codes Sources
A voir également
- Algorithme d'euclide étendu python
- Algorithme d'euclide python - Meilleures réponses
- Euclide étendu python - Meilleures réponses
- Algorithme d'euclide étendu - Guide
- Python : Bézout ou algorithme d'euclide étendu - CodeS SourceS - Guide
- Algorithme d'euclide python - Guide
- Algorithme d'euclide en c - Guide
- Un petit programme qui calcule le pgcd via l'algorithme d' euclide :o) - Codes sources - C / C++ / C++.NET (Divers)
Commentaires
- Messages postés
-
107
- Date d'inscription
- mardi 30 juillet 2013
- Statut
- Membre
- Dernière intervention
- 17 avril 2019
7L'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
164 72 20 12 8 4
-2 -3 -1 -1
(16) (-7) 2 -1 1
tableau très facile à remplir..
***Modération CCM
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.