Pour nos amies les TI...

Et oui, je cède à la vindicte publique, et vous propose une solution pour ceux combinant une TI et l'arithmétique de spé math.

En effet, les TI ne font pas à ma connaissance les congruences, mais tonton Cyber est là pour vous apporter non pas une mais plusieurs solutions pour calculer

52⁷⁷ (mod 95) ou plus simplement 198 (mod 23) !

On va de suite commencer par réaliser un programme faisant juste les congruences. Dans ce qui suit, ce qui est en gras est ce qui est sur la calculette, ce qui est en italique est une précision sur l'emplacement de commandes et ce qui est souligné est une indication sur ce que fait la ligne en question.

Il faut tout d'abord créer un nouveau programme que vous appellerez comme vous voulez, et vous incrirez le programme suivant :

:Prompt A,B        (Prompt est dans PRGM, I/O) permet de rentrer A et B (le modulo)
:A-B*IPart(A/B)→A    (IPart est la partie entière d'un nombre on la trouve dans MATH, NUM; → est la touche STO pour stocker)
:Disp A                (Disp est aussi dans PRGM, I/O) affiche A, le résultat

Comment marche ce programme : en fait, on enlève le plus de fois possible B dans A grâce à la partie entière, ce qui est le but de la congruence. La preuve par l'exemple : on cherche 33 (mod 6)
Int(33/6) = 5
et 33-6*5 = 3 et on vérifie facilement que 33=3 (mod 6).

On va maintenant passer au modulo exponentiel pour calculer 52⁷⁷ (mod 95) :

Là je vous propose plusieurs solutions.

La première est faire une boucle jusqu'à l'exposant souhaité : si je veux avoir a³ (mod n), je calcule a*a (mod n) que je stocke dans A, puis je calcule A*a (mod n) que je stocke de nouveau dans A et j'ai obtenu ce que je voulais. On peut donc faire le programme suivant :

:Prompt A,B,C    (ici A est le nombre exposant B modulo C)
:A→D          (permet de différencier A et le nombre originel)
:For(E,2,B)    (For est dans PRGM) Pour E allant de 2 à B
:A*D-C*Ipart(A*D/C)→A    permet de faire A^E+1 (mod C)
:End          (End est dans PRGM) signale la fin de la boucle
:Disp A

Ce programme marche mais l'inconvénient est que plus l'exposant est grand, plus c'est long... des gens y ont déjà réfléchi et donc ils ont inventé la méthode de l'exponentiation rapide dont voici le programme

:Prompt A,B,C   (ici A est le nombre exposant B modulo C)
:1→D
:While B≠0      (While est dans PRGM et ≠ dans TEST, regarder sur les touches ou juste au-dessus pour le trouver)
:If Frac(B/2)=0        (If est dans PRGM, = dans TEST, Frac est dans MATH, NUM) Autrement dit, si B est pair
:Then                (Then n'est jamais loin de If) 
:B/2→B
:Else                (Else non plus)
:A*D-C*Int(A*D/C)→D     A*D (mod C)
:(B-1)/2→B
:End                        Signale la fin de la boucle If
:A²-C*Int(A²/C)→A       A² (mod C)
:End                       Signale la fin de la boucle While
:Disp D

Alors comment ça marche ? Et bien ce n'est pas si compliqué, il faut d'abord décomposer l'exposant en somme de puissances de 2 (ex : 13 = 8+4+1) et si vous regardez bien, vers la fin, on fait à chaque fois A² mod C, ce qui fait que si on part du nombre du début, on a A mod C, A² mod C, A⁴ mod C, A⁸ mod C... les exposants sont des puissances de 2. Il suffit donc de multiplier les congruences des exposants qui nous intéressent (pour A¹³ il faut A⁸*A⁴*A mod C) et le tour est joué.

Voilà. Si vous avez des commentaires, critiques, remarques, je suis à votre écoute.