Formule d'inverse modulaire

Tout dépend de ce que tu entends par "formule". Par exemple, et pour prendre un cadre un peu plus général, il n'est pas difficile de montrer que la solution dans $\{0,\dotsc,n-1\}$ de l'équation $ax \equiv b \pmod n$, avec $\textrm{pgcd}(a,n)=1$, est donnée par
$$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.

À part celle que je t'ai donné ci-dessus, là, comme ça, ça ne me dit rien...Et j'irais même jusqu'à dire que l'intérêt d'une telle formule m'échappe, puisque l'algorithme d'Euclide (appelé parfois "Euclide étendu") fait le job.

Salut,

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

Le tout est de savoir si Al-Kashi souhaite une formule "pour le plaisir" ou une réalisable en pratique (i.e. pas trop dépensière en algo). L'idée proposée par Aurel est intéressante surtout d'un point de vue théorique.

Il faudrait qu'il nous dise quel est son objectif.

Et comment calcule-t-on $\varphi(n)$ ?

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é".

Bonjour,

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.

Citation GaBuZoMeu :
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.

Bonjour,

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