Un algorithme de calcul d'un inverse
Je dispose d'un algorithme de calcul dont je souhaite démontrer la validité.
Pour l'illustrer, je considère l'exemple de la détermination de l'inverse de $\bar8$ dans $\mathbb{Z}/37\mathbb{Z}.$
On obtient successivement :
\begin{align*}\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} 1 & -1 \\ {\color{Blue}-1}& 2 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -4 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix}\\[1mm]
\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} -1 & 2 \\ {\color{Blue}2} & -3 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -4 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix} \\[1mm]
\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} 2 & -9 \\ {\color{Blue}-3} & (-3)\times(-4)+2 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix}\end{align*}
L'algorithme que je propose consiste simplement à écrire :
..............-4..........-1............-1.............-1
................a.........−3...........2...............−1..................1..........0
Sur la deuxième ligne, on écrit les quotients des divisions euclidiennes successives.
Puis on écrit les opposés des quotients toujours sur la deuxième ligne (d'où les -).
Enfin, sur la troisième ligne, on commence par la droite en écrivant "1........0" et on complète progressivement vers la gauche en faisant successivement :
(-1)*1+0=-1
(-1)*(-1)+1=2
(-1)*2+(-1)=-3
et enfin a=(-4)*(-3)+2, qui fournit l'inverse de $\bar8$ dans $\mathbb{Z}/37\mathbb{Z}$.
Cordialement.
________________________
Remarque : j'avais déjà exposé cet algorithme dans un autre post mais comme il était noyé parmi d'autres informations, je me permets de le reposter ici.
Réponses
-
Comme tu l'écris, trouver un inverse dans $\mathrm{Z} / p \mathrm{Z} $ c'est déterminer une relation de Bézout. C'est donc en fait l'algo d'Euclide.---> I believe in Chuu-supremacy : https://www.youtube.com/watch?v=BVVfMFS3mgc <---
-
@Positif : bonjour. En effet, il s'agit de l'algorithme d'Euclide étendu, de toute évidence. Ce que je cherche depuis quelques semaines voire quelques mois- en dillettante, il est vrai-, c'est une démonstration du fait que l'algo proposé (sans latex) fournira le même résultat que l'algorithme proposé par François Liret par exemple (avec $\rm\LaTeX$).
-
Voici un premier jet de démonstration : quand on analyse l'algorithme de François Liret, on se rend compte que, pour le problème qui nous occupe, seuls importent les coefficients $M_{2,1}$ et $M_{2,2}$ des matrices, autrement dit les coefficients de la deuxième ligne. Quand on calcule progressivement les produits de matrices $2\times2$, que se passe-t-il? $M_{2,2}$ vient prendre la place de $M_{2,1}$ et la nouvelle valeur de $M_{2,2}$ est $M_{2,1}+M_{2,2}\times(-q_i)$ et c'est exactement ce qui se passe dans le cadre de l'algorithme présenté sans latex.
-
Déjà entièrement détaillé :Si tu veux écrire ça avec des matrices, il faut comprendre que ce n'est qu'une autre présentation de l'algo d'Euclide étendu (en gros on manipule deux lignes de coefficients à chaque étape pour obtenir les deux suivantes). J'avais fait un petit exo où on prouve l'algorithme et où on prouve sa complexité "pire des cas" (en pièce jointe)
-
@troisqua : bonjour, j'ai parcouru le post d'Oshine et les commentaires, ainsi que tes pièces jointes. Mais je ne trouve nulle part la présentation claire fournie par l'algorithme :
37..........8...........5..............3...............2....................1
..............-4..........-1............-1.............-1
................a.........−3...........2...............−1..................1..........0
que j'ai expliqué dans mon post.
Aussi, je ne considère pas que la réponse que j'attends y soit "entièrement détaillée".
Par ailleurs, j'ai parfaitement compris que l'écriture matricielle n'est qu'une autre présentation de l'algorithme d'Euclide, ce qui n'est pas difficile à comprendre.
-
Ce que j'écris dans mon papier revient à écrire
\begin{eqnarray*} a & = & 37\\ b & = & 8\left(q=4\right)\\ a-4b & = & 5\left(q=1\right)\\ -a+5b & = & 3\left(q=1\right)\\ 2a-9b & = & 2\left(q=1\right)\\ -3a+14b & = & 1 \end{eqnarray*} donc l'inverse de $\overline{8}$ dans $\mathbb{Z}/37\mathbb{Z}$ est $\overline{14}$. La présentation matricielle de ce que je viens d'écrire c'est ce que tu écris mais ça n'apporte rien au calcul précédent et ça cache le fonctionnement de l'algorithme (qui consiste juste à diminuer le plus vite possible une combinaison de $a$ et de $b$ pour obtenir la plus petite). Je pense que toute autre méthode ou présentation revient à faire les mêmes calculs mais en plus long... (sauf si on fait la petite variante consistant à autoriser des restes négatifs) qui donnerait : \begin{eqnarray*}a & = & 37\\ b & = & 8\left(q=5\right)\\ a-5b & = & -3\left(q=-3\right)\\ 3a-14b & = & -1 \end{eqnarray*} donc l'inverse de $\overline{8}$ dans $\mathbb{Z}/37\mathbb{Z}$ est $\overline{14}$. Bref, deux lignes suffisent -
@troisqua : ça a l'air en effet de bien fonctionner . On trouve l'explication dans les pièces jointes ?
un défi :
1261........23........19..........4..........3........1
.................-54......-1..........-4.........-1
..................a.........-6............5........-1........1.......0
L'inverse de 23 dans Z/1261 est -54. (exemple pris au plus grand des hasards)
ça reste performant ?
-
Tu as fait une (des ?) erreur(s) de calcul.
\begin{eqnarray*}a & = & 1261\\ b & = & 23\left(q=54\right)\\ a-54b & = & 19\left(q=1\right)\\ -a+55b & = & 4\left(q=5\right)\\ 6a-329b & = & -1 \end{eqnarray*} Bref, 3 lignes : l'inverse est 329 (modulo 1261).
C'est exactement le même algorithme que toi, t'en rends-tu compte ? (mis à part que j'autorise des restes négatifs pour descendre le plus vite possible). Dans les pièces jointes, on démontre que l'algorithme donne une relation de Bézout, et on montre sa performance (qu'on majore en fonction du nombre de chiffres de $b$).
-
@troisqua : l'inverse de 23 dans Z/1261 n'est pas -54 mais (-54)*(-6)+5=329. Nous sommes ok.
Si les deux algorithmes sont les mêmes, tant mieux; mais je t'avoue qu'avec tes $a$ et tes $b$ et tes $q$ non explicités, je ne m'en rends pas compte. Je lirai à tête reposée tes pièces jointes. En particulier le calcul de performance m'intéresse. merci. -
stfj : tu veux une relation de Bézout entre $a$ et $b$ strictement positifs donc tu cherches une combinaison $au+bv$ minimale non nulle. Donc tu démarres avec deux combinaisons évidentes : $a=a$ et $b=b$ (les deux premières lignes) puis tu cherches à faire diminuer cette combinaison en cherchant combien de fois tu peux retirer $b$ de $a$ (c'est ça $q$). Tu fais alors première ligne moins $q$ fois la deuxième. Et ainsi de suite (c'est ça que tu fais avec tes matrices 2x2)
-
Cool
-
Bonjour stfjLe sujet a été abordé récemment dans le fil inversibles dans $\Z/n\Z$. Il existe d'autres méthodes pour calculer un inverse modulaire.Par exemple, si tu cherches l'inverse de $8$ modulo $37$, tu peux écrire:$\overline{8^{-1}}=37\Big(\dfrac{1}{37*8}-\dfrac{1}{8*5}+\dfrac{1}{5*3}-\dfrac{1}{3*2}+\dfrac{1}{2*1}\Big)$.Comme je l'ai déjà précisé, si tu souhaites programmer cet algorithme et même en pratique, on peut ne pas tenir compte des restes successifs dont le produit est supérieur à $n$.Une autre méthode applicable ici, car $37$ est un nombre premier: $37=8*4+5=7*5+2=18*2+1$.Tu obtiens alors $\overline{8^{-1}}=-4*(-7)*(-18)=-504\equiv 14 \mod 37$
Al-Kashi
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres