Formule d'inverse modulaire
dans Arithmétique
Bonjour,
Pendant mes recherches sur le théorème de Popoviciu, je me suis posé la question suivante:
Existe-t-il une formule pour l'inverse modulaire d'un nombre?
Il semblerait qu'une telle formule existe et qu'elle améliore légèrement l'algorithme d'Euclide étendu mais je ne la retrouve pas dans les différents articles que j'ai parcourus.
Auriez-vous des référencesconnues pour une formule pour l'inverse modulaire.
En vous remerciant,
Al-Kashi
EDIT
J'ajoute en fichier joint la formule inédite il me semble que je vous propose.
Si vous pensez que celle-ci est intéressante alors je compléterai le document progressivement.
Pendant mes recherches sur le théorème de Popoviciu, je me suis posé la question suivante:
Existe-t-il une formule pour l'inverse modulaire d'un nombre?
Il semblerait qu'une telle formule existe et qu'elle améliore légèrement l'algorithme d'Euclide étendu mais je ne la retrouve pas dans les différents articles que j'ai parcourus.
Auriez-vous des référencesconnues pour une formule pour l'inverse modulaire.
En vous remerciant,
Al-Kashi
EDIT
J'ajoute en fichier joint la formule inédite il me semble que je vous propose.
Si vous pensez que celle-ci est intéressante alors je compléterai le document progressivement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$$x = ub - n \left \lfloor \frac{ub}{n} \right \rfloor$$
où $u \in \mathbb{Z}$ est une solution de $au+nv=1$. Bien que cette formule fournisse immédiatement, via Euclide, un algo pour déterminer $x$, je doute que ce soit ça que tu cherches.
Ce que je sous entends par formule, c'est une expression du type $a^{-1}=... $ ou le membre de droite est explicite.
Aurais-tu déjà rencontré une telle formule?
J'ai été tellement étonné et surpris de l'élégance de cette formule même si dans la pratique elle ne me semble améliorer que légèrement l'algorithme d'Euclide étendue.
En te remerciant,
Al-Kashi
Al-Kashi, ta formule qui donne l'inverse de $a$ modulo $n$ ($a$ et $n$ étant étrangers) utilise-t-elle l'ordre de $a$ modulo $n$ (lequel ordre divise $\varphi(n)$) et/ou l'ordre de $n$ modulo $a$ ou ni l'un ni l'autre?
Cordialement
Paul
Si je ne dis pas de bêtise (on est dimanche matin...), pour $a$ inversible modulo $n$ on a $a^{\phi(n)}=1 \bmod{n}$ donc $a^{-1} = a^{\phi(n)-1} \bmod{n}$. Je ne sais pas si ça rentre dans tes "formules" autorisées.
Amitiés,
Aurel
Bêtises mises à part.
Cordialement
Paul
Il faudrait qu'il nous dise quel est son objectif.
@depasse: En fait , comparativement aux méthode qui sont proposées là:
algorithme-inverse
la formule que j'ai trouvée ne ressemble aucune de celles-ci.
@noix de totos: Je dirai que c'est à la fois une belle formule à mon goût et à priori utilisable en pratique mais seuls les amateurs de codes pourront le confirmer en comparant les complexités
Bon je vais essayer d'écrire un truc clair pour avoir votre avis sur l'intérêt ou non d'une telle formule.
Al-Kashi
Heureusement que les logiciels de calcul formel n'utilisent pas cette formule (j'ai arrêté le calcul de l'indicatrice d'Euler de $3^{333}+14$ après que la bécane ait mouliné et ventilé un bout de temps sans succès).
P.S. Une âme charitable me signale qu'il faut écrire "après que la bécane eut mouliné" (sans accent circonflexe, surtout pas de subjonctif !) et non pas "après que la bécane ait mouliné".
Al-Kashi n'a pas encore donné sa formule!
Je rappelle qu'être capable de calculer $\phi (n)$ revient à être capable de casser RSA.
Donc je conseille @Al Kashi, de partager d'abord sa formule (en MP) avec Noix de Totos par exemple avant de la rendre publique, car elle pourrait faciliter certains calcul à usage délictueux (cryptanalyse).
Bonne soirée.
J'ai juste illustré le fait que la formule d'aurelpage n'a aucun intérêt pratique, ce avec quoi tout le monde est bien d'accord.
J'ai juste illustré le fait que la formule d'aurelpage n'a aucun intérêt pratique, ce avec quoi tout le monde est bien d'accord.
Bien sûr qu'elle a un intêret (quand on sait calculer $\phi$).
Citation :
Al-Kashi n'a jamais prétendu calculer l'indicatrice d'Euler avec sa formule.
Une solution nouvelle ouvre des perpespectives nouvelles, et je maintiens le conseille fait à Al Kashi.
Bonne soirée.
J'ai ajouté le fichier en pièce jointe dans le premier message.
Je n'ai pas beaucoup de temps pour tout détailler, mais si le résultat vous semble intéressant alors je compléterai progressivement.
En vous remerciant,
Al-Kashi
Al-Kashi écrivait : « Existe-t-il une formule pour l'inverse modulaire d'un nombre?
Il semblerait qu'une telle formule existe et qu'elle améliore légèrement l'algorithme d'Euclide étendu mais je ne la retrouve pas dans les différents articles que j'ai parcourus. »
Il y a plus d’un an je rédigeais un petit programme informatique qui nécessitait une routine de calcul de l’inverse modulaire. En cherchant sur internet j’ai découvert l’algorithme suivant (désolé, je n’ai pas retenu une quelconque référence) :
Soit p>3 un nombre premier et 2 < a < p-1 le nombre entier à inverser. (L’inverse de 2 est (p+1)/2 et l’inverse de p-1 est p-1 : il n’y a pas de calcul à faire)
On utilise la suite auxiliaire d’entier suivante :
A(0) := p^2
A(1) := a*p+1
Et pour n>0, A(n+1) := A(n) mod A(n-1)
Le premier terme de cette suite inférieur à p est l’inverse recherché.
Exemple numérique 1 :
Quel est l’inverse de 10 modulo 101 ?
A(0) = 10201
A(1) = 1011
A(2) = 91 < 101
Donc 91 est l’inverse de 10 : 91 x 10 = 910 = 909 +1 = 1 [101 ]
Exemple numérique 2 :
Quel est l’inverse de 10 modulo p = 10^20 + 39 (qui est un nombre premier)?
On a :
A(2) = 890000000000000000348
A(3) = 110000000000000000043
A(4) = 10000000000000000004 < p
Donc l’inverse de 10 est 10000000000000000004
Je n’ai pas de démonstration de cet algorithme mais … ça marche !
Dans son document Pdf, Al-Kashi se proposait d’inverser 53 modulo 341.
Notons que 341 n’est pas un nombre premier : 341 = 11 x 31
A(0) = 116281
A(1) = 18074
A(2) = 7837
A(3) = 2400
A(4) = 637
A(5) = 489
A(6) = 148 < 341
L’inverse de 53 est 148 : 53 x 148 = 7844 = 7843 +1 = 23*341 + 1 = 1 [341]
Vu le peu d’opérations nécessaires, je ne sais pas si cet algorithme est optimisé.
Si un tel algorithme optimal existe, il me semble qu’il doit être concis (entendez performant !)
Je modère cependant mon dernier propos :
GaBuZoMeu se proposait d’inverser (2^222+13) modulo (3^333+14).
Pour retrouver le même résultat, j’ai dû calculer 134 étapes intermédiaires ! de A(2) à A(136) :
A(136) = 323350776989884409192488090711498105642230107380260792953739253766596683624910934179982764919010048602122458336152634623669067022770198377025528257085581912584
https://sites.google.com/site/barryrsmith/barryriedsmith/pubsandpreprints
C'est dans le pdf de l'item 5.
Al-Kashi