Algorithme d'Euclide étendu
3/5 (2 avis)
Vue 15 212 fois - Téléchargée 1 693 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
- Euclide étendu python - Meilleures réponses
- Algorithme euclide étendu python - Meilleures réponses
- Python : Bézout ou algorithme d'euclide étendu - CodeS SourceS - Guide
- Algorithme d'euclide étendu - Guide
- Algorithme d'euclide pgcd python - Guide
- Python : Coefficients de Bézout et algorithme d'Euclide en matriciel - CodeS SourceS - Guide
- Algorithme d'euclide pgcd en c - Guide
- Messages postés
-
111
- Date d'inscription
- mardi 30 juillet 2013
- Statut
- Membre
- Dernière intervention
- 4 décembre 2021
1224 févr. 2018 à 10:32
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
Modifié le 8 juin 2018 à 15:59
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.