Une trouvaille: l'inverse modulaire revisité
dans Arithmétique
Arithméticiens, arithméticiennes,
Actuellement, l'algorithme le plus utilisé à ma connaissance est l'algorithme d'Euclide étendu.
Je vous propose à travers cet exercice de découvrir une méthode inédite permettant de trouver l'inverse modulaire d'un nombre.
Les spécialistes pourront ensuite dire si une telle méthode apporte quelque chose de nouveau.
On considère deux entiers $a$ et $b$ premiers entre eux strictement supérieurs à $1$
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
On note $(a^{-1})_b$ l'inverse de $a$ modulo $b$ et on note $(b^{-1})_a$ l'inverse de $b$ modulo $a$
Soit la suite $U_k$ définie par $U_0=ab+1$ et $U_{k+1}=U_k-(U_k)_a-(U_k)_b$
On note $m$ le plus petit entier tel que $U_m=0$
Démontrer que $(a^{-1})_b=\sum \limits_{k=0}^{m}(-1)^k \Big\lfloor \dfrac{U_k}{a}\Big\rfloor$ et $(b^{-1})_a=\sum \limits_{k=0}^{m}(-1)^k \Big\lfloor \dfrac{U_k}{b}\Big\rfloor$
Amusez-vous bien,
Al-Kashi
Actuellement, l'algorithme le plus utilisé à ma connaissance est l'algorithme d'Euclide étendu.
Je vous propose à travers cet exercice de découvrir une méthode inédite permettant de trouver l'inverse modulaire d'un nombre.
Les spécialistes pourront ensuite dire si une telle méthode apporte quelque chose de nouveau.
On considère deux entiers $a$ et $b$ premiers entre eux strictement supérieurs à $1$
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
On note $(a^{-1})_b$ l'inverse de $a$ modulo $b$ et on note $(b^{-1})_a$ l'inverse de $b$ modulo $a$
Soit la suite $U_k$ définie par $U_0=ab+1$ et $U_{k+1}=U_k-(U_k)_a-(U_k)_b$
On note $m$ le plus petit entier tel que $U_m=0$
Démontrer que $(a^{-1})_b=\sum \limits_{k=0}^{m}(-1)^k \Big\lfloor \dfrac{U_k}{a}\Big\rfloor$ et $(b^{-1})_a=\sum \limits_{k=0}^{m}(-1)^k \Big\lfloor \dfrac{U_k}{b}\Big\rfloor$
Amusez-vous bien,
Al-Kashi
Réponses
-
Pardon, Al - Kashi, mais avant de m'intéresser à ta question, comment t'y prends-tu pour calculer l'inverse d'un nombre modulo un autre ?
Je te pose cette question, parce que utiliser Euclide pur et dur n'est pas forcément le plus rapide ... -
Hello,
Je ne sais pas si j'ai raté un chapitre mais avec $a = 1$ et $b = 2$. N'aurait-on-pas :
$U_0 = 3$
$U_1 = 3 - 0 - 1 = 2$
$U_2 = 2 - 0 - 0 = 2$
$U_3 = 2 - 0 - 0 = 2$
...
J'espère que je me trompe.
D'ailleurs pour $a = 2$ et $b = 4$ :
$U_0 = 9$
$U_1 = 9 - 1 - 1 = 7$
$U_2 = 7 - 1 - 3 = 3$
$U_3 = 3 - 1 - 3 = -1$
$U_4 = -1 + 1 + 1 = 1$
$U_5 = 1 - 1 - 1 = -1$
... -
@Adaq
Non tu ne te trompes pas, je dois juste corriger l'énoncé en enlevant les cas élémentaires $a=1$ ou $b=1$.
@Nodgim
J'ai le plus souvent utilisé Euclide Étendu même si je sais qu'on peut aussi utiliser le théorème d'Euler dans certains cas ou cela est plus rapide. Maintenant niveau rapidité algorithmique je ne peux rien dire
Al-Kashi -
Ah pardon, je n'ai rien dis alors.
C'est excellent, je suis en train de tester pour toutes les combinaison $(i,j)$ de 1 à 1'000'000'000 et ça à l'air de marcher.
J'ai hâte de voir la démonstration. Par contre pour le calculer à la main je suppose que ça n'a pas beaucoup d’intérêt à cause de la somme qui peut être longue. A moins que tu aies une valeur maximale pour $m$.
Je vais comparer avec Euclide étendu pour voir si il y en a un plus rapide que l'autre pour de très grand nombre. -
En tout cas, ce n'est pas possible que l'algorithme que tu proposes soit plus rapide que celui-ci.
Exemple : 45 et 79
1*45 = + 45
1*45 = - 34
2*45 = + 11
3*(2*45) + 1*45 = 7 * 45 = 33-34 = -1
-7 * 45 = 72*45 = 1
(72*45-1) / 79 = 41
72*45 - 41*79 = 1 -
Il n'a pas de nom particulier que je sache, c'est une présentation personnelle.
Je ne comprends pas la question de la complexité, l'exemple ne suffit il pas à comprendre la démarche ? -
La complexité c'est le "temps" dont on a besoin pour l'exécuter, par exemple celui d'Al-Kashi est de l'ordre de $O(m)$ car la plus longue opération dépend de $m$, ici c'est une somme d'élément calculable avec un nombre constant d'opération (disons 3, l'arrondissement de la division, la division et la multiplication), on a donc $O(m) * O(3) $ qui appartient à $O(m)$. Le mieux serait évidement de la déterminer en fonction de $a$ et de $b$ mais je n'ai pas essayé.
Et non je ne peux déterminer la complexité d'un algorithme à partir d'un seul exemple, mais ce n'est pas très important c'était juste pas curiosité. -
Al Kashi va jusqu'à ce que Um = 0, or vu l'algo, si b > a, il doit faire " a " opérations pour trouver l'inverse de " b " .
Donc pour des grands nombres, ça doit commencer à compter en temps.
Cela dit, ne pourrissons pas plus sa question avec cette digression, il y a quand même cette propriété remarquable à prouver. -
Effectivement, il faut mettre la complexité de côté. Et mettre $a\N + b\N$ sur la sellette.
[color=#000000] > a := 10^7 + 1 ; > b := 10^7 - 1 ; > time Modinv(a,b) ; <-- magma 5000000 Time: 0.000 > time a1,b1 := Inverses(a,b) ; <-- Al-Kashi Time: 20.600 > a1 ; 5000000 [/color]
Of course, ci-dessous, inutile de solliciter Inverses[color=#000000] > a := 10^50 + 1 ; > b := 10^50 - 1 ; > time Modinv(a,b) ; 50000000000000000000000000000000000000000000000000 Time: 0.000 [/color]
-
$U_k \mapsto U_{k+1}$ se décrit en terme de la suite $(x_{k+1},y_{k+1}) =(\lfloor y_k b/a \rfloor, \lfloor x_k a/b \rfloor)$
donc
$(ax_{k+1},by_{k+1}) = (X_{k+1},Y_{k+1}) =(a\lfloor Y_{k}/a \rfloor, b \lfloor X_k/b \rfloor)$ -
Bonsoir à tous,
Tout d'abord merci pour votre participation et l'intérêt que vous portez à ce sujet.
Je vois que pour l'instant les discussions ont tourné autour de la complexité.
Je vous fournis donc mon meilleur résultat.
On se place dans le cas où l'on cherche l'inverse de $a$ modulo $b$
On arrête l'algorithme dès que $(U_g) _a=0$.
On a alors $(a^{-1})_b=\sum \limits_{k=0}^{g}(-1)^k \Big\lfloor \dfrac{U_k}{a}\Big\rfloor$
Même avec cette amélioration, je pense que je serais loin derrière magmaX:-(
Al-Kashi -
Comment calcules-tu le reste dans une division euclidienne sans l'algorithme d'Euclide (qui n'est pas moins coûteux que l'algorithme d'Euclide étendu) ?
-
J'ai une demi-réponse pour cette question, c'est une prolongation de ma réponse à la question précédente. Comme tu avais indiqué ne pas l'avoir comprise en entier, ça va être compliqué de m'expliquer.....
Je reprends quelques extraits de la description précédente :
La sous-suite x0, x2, x4 est donc une suite arithmétique de raison r [ a ]. Elle aboutit à 0 puisque b premier avec a, donc r premier avec a.
........
En partant du couple (r, b-r) on aboutit à 0 par une chaine unique qui contient toutes les valeurs x modulo a et toutes les valeurs y modulo b > b-a.
Or r = a - b [a] = -b[a] En suivant les x successifs, on arrivera bien à x = 1. Quand on arrivera à cette valeur, on aura l'égalité k * r = 1 soit k * ( -b[a] ) = 1
Si k est l'inverse [a] de -b, alors -k est l'inverse de b, et -k c'est a-k, c'est à dire le reste des valeurs de " a " entre 1 et 0.
Or il se trouve que, pour b [a] [U(k+1)/b] = [Uk/b] - 1. En prenant la soustraction de 2 Uk successifs, on obtient 1. Or, dans la chaine que j'avais décrite, les r [a] apparaissent un fois sur 2.
" -k " représente donc exactement la valeur de la suite proposée.
Pour la suite des Uk / a, avec a < b , je n'ai aucune idée de la raison pour laquelle ça marche également. -
Voici la réponse:
Nous utilisons toujours:
Lemme :
Soit $n$ un nombre entier.
Les équations $ax+by=n $ $(1)$ et $ai+bj=n-(n)_a-(n)_b$ $(2)$ ont le même nombre de solutions.
On définit alors la suite $U_k$ telle que $U_0=ab+1$ et $U_{k+1}=U_k-(U_k)_a-(U_k)_b$
On prouve tout d'abord aisément que l'unique solution de l'équation $ax+by=U_0$ est $\Big((a^{-1})_b;(b^{-1})_a\Big)$
On prouve alors aisément que pour tout $U_k$ l'équation $ax+by=U_k$ possède une unique solution.
On note alors $(x_k;y_k)$ cette unique solution.
On a les relations $x_{k}=\Big\lfloor\dfrac{U_k}{a}\Big\rfloor-x_{k+1}$ et $y_{k}=\Big\lfloor\dfrac{U_k}{b}\Big\rfloor-y_{k+1}$
Une récurrence permet de conclure.
J'en reviens à ma question initiale, que vaut cette trouvaille:
1) Rien et elle restera sur un forum.
2) Elle est intéressante et peut faire l'objet d'un petit encadrée dans une petite revue mathématiques .
Al-Kashi -
Original en tout cas !
Après, au gré des modes et des influences sur les publications..... -
Bon allez, je me contenterai d'un bel échange sur un forum :-D
J'avais aussi à l'époque,en utilisant un raisonnement élémentaire, proposé de nouvelles identités proches des identités de Popoviciu et Tripathi mais je n'ai jamais eu de retour.
Je pense que cela doit être compliqué pour des amateurs de proposer des choses, à moins d'exploser le plafond en résolvant un problème d'Hilbert(:P)
Al-Kashi -
En continuant mes recherches et en utilisant une autre méthode j'ai obtenu une autre relation aussi sous forme de somme qui me semble plus intéressante . Il me semble que cette méthode est bien plus rapide que la précédente.
Je vais tenter de vous l'exposer prochainement.
Al-Kashi -
Salut melpomène,
Honnêtement comme je l'ai dit plus haut, il me semble difficile en tant qu'amateur de proposer des choses même nouvelles.
En attendant je les propose donc sur ce forum que j'apprécie beaucoup et qui permet dans un premier temps de discuter de l'intérêt ou non de tel ou tel résultat.
Ps: Place à l'acte 2...
Al-Kashi -
RMS et Quadrature n'ont pas vocation à publier des choses nouvelles, mais plus des résultats intéressants ou des approches un peu originales de résultats existants, démontrés à l'aide d'outils mathématiques ne dépasse pas un bon niveau L2/Prépa, voire L3 pour Quadrature.
Je trouve donc dommage que tu t'auto-censures, surtout que tes travaux entrent parfaitement dans ce cadre...
Mel -
@Al-Kashi
Pareil que Mel d'une part. D'autre part, pourquoi vouloir mettre en avant cette histoire de rapidité ? Je ne suis pas convaincu qu'il faille le présenter ainsi.
Autre chose. A force de ``cacher un peu tes affaires'' (par exemple donner des ``exercices'' dont tu as la solution via quelque chose de structurel), ce n'est pas toujours facile d'échanger. Je prends un exemple concret sur l'autre fil (flemme de pointer) mais qui présente des analogies avec ce fil (et pour cause).
Contexte : $a, b \in \N^*$ premiers entre eux. Je note $b^{-1}$ un inverse de $b$ modulo $a$, $a^{-1}$ un inverse de $a$ modulo $b$, $n_a$ le reste de $n$ dans la division par $a$. Idem pour $n_b$. Et enfin $\{ x \} = x - \lfloor x\rfloor$ (la partie fractionnaire je crois que cela s'appelle comme cela). Cette histoire d'invariance de $\#\{(x,y) \in \N \times \N \mid ax + by = n\}$ par $n \mapsto n - n_a - n_b$, tu étais le seul à la connaître. J'ai gratté dans mon coin et j'ai fini par trouver (pas de manière super limpide à vrai dire) ``un certain pot aux roses''. Mais ce n'était pas ton invariance ! Et quand j'ai voulu vérifier des choses en tenant compte de la formule de Popoviciu, je me suis rendu compte que cela me conduisait à l'identité :
$$
\left\{ {b^{-1} (n - n_a - n_b) \over a} \right\} = \left\{ {a^{-1} n \over b} \right\} - {n_b \over ab}
$$
J'ai bien essayé de montrer cette égalité de manière directe mais je n'y suis pas arrivé (à vrai dire, je n'ai pas trop insisté). Est ce qu'elle te dit quelque chose ? -
@Claude et @Melpomène
En tant qu'amateur, c'est vrai qu'à force on se dit que c'est inutile et qu'on crée une sorte d'auto-censure.
Allez, je vais retenter avec Quadrature et RMS. Je vais essayer de mettre cela en forme et de le proposer.
@Claude
J'ai aussi obtenu pas mal de résultats assez drôles mais pas celui que tu proposes car j'ai travaillé à partir des résultats que j'avais obtenus assez proches de Tripathi. Avec ces belles et drôles de relations, mon objectif était d'extraire une relation close pour l'inverse modulaire mais sans succès.
Al-Kashi -
Bonsoir
Il y a quelques mois j'avais proposé ici une formule pour déterminer un inverse modulaire http://www.les-mathematiques.net/phorum/read.php?5,1740974,1740974#msg-1740974
[À la demande de l'auteur, discussions fusionnées. AD]
Il s'agit ici d'un complément qui permet d'éviter de calculer la somme indiquée et de tout simplement raisonner sur un indice de la suite.
Plus précisément, on suppose que $a>b$ premiers entre eux. On définit la suite $U_{k+1}=U_k-(U_k)_b-(U_k)_a$ avec $U_0=ab+1$ et on note $g$ le plus petit entier tel que $(U_g)_b=0$.
Si $g$ est pair alors $(a^{-1})_b=\dfrac{g}{2}$.
Si $g$ est impair alors $(a^{-1})_b=b-\dfrac{g-1}{2}$.
Al-Kashi -
Salut, ça semble vrai mais on doit vérifier à chaque étape $(U_i)_b$ donc une division Euclidienne.
-
Bonjour Tonm,
En fait, comme cela avait été signalé par Claude dans la discussion initiale, la complexité est à mettre de côté. En faisant quelques essais, on se rend vite compte que l'algorithme n'a aucun intérêt sur le plan pratique.
Al-Kashi -
Bonjour, je ne sais sa véracité (ou vrai j'étais rapide en haut) elle semble nouvelle si juste.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 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
- 63 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
- 313 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
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres