6XC

Calculateur d'arithmétique modulaire

Calculez a mod n, l'addition modulaire, la multiplication et la puissance (aᵇ mod n) — l'arithmétique de l'horloge instantanément.

1 228 vues

Comment fonctionne l'arithmétique modulaire

a mod n pose une question simple : quel reste subsiste après avoir divisé a par n ? Formellement, a mod n = a − n × plancher(a ÷ n), et par convention mathématique, le résultat se situe toujours entre 0 et n−1. La façon la plus intuitive de se représenter cela est le cadran d'une horloge : les heures ne comptent pas indéfiniment, elles bouclent à 12 (ou 24). Supposons qu'il soit 15h00 et que vous deviez connaître l'heure 10 heures plus tard — vous n'obtenez pas « 25h00 », vous calculez (15 + 10) mod 24 = 1, soit 01h00 le lendemain. Chaque valeur reboucle à travers le même ensemble de « cases », et ce bouclage est exactement ce que fait n dans a mod n.

Ce calculateur étend la même idée à trois opérations apparentées : l'addition modulaire (a + b) mod n, la multiplication modulaire (a × b) mod n, et l'exponentiation modulaire aᵇ mod n. Cette dernière paraît anodine, mais c'est l'opération la plus importante de la cryptographie moderne. La calculer naïvement — élever d'abord a à la puissance b, puis prendre le reste — produirait des nombres de plusieurs millions de chiffres pour des tailles de clés réelles, bien avant que l'étape modulo n'intervienne. À la place, l'outil utilise l'algorithme d'exponentiation rapide par élévation au carré (square-and-multiply) : il élève répétitivement la base au carré et réduit modulo n à chaque étape, si bien que les nombres intermédiaires ne dépassent jamais la taille de n lui-même, quelle que soit la grandeur de b. C'est ce qui rend possibles des résultats exacts même pour des exposants de plusieurs centaines de chiffres.

Ce qu'il faut savoir

  • Cryptographie : l'échange de clés RSA et Diffie-Hellman reposent tous deux sur l'exponentiation modulaire avec de très grands nombres premiers — chiffrer un message revient essentiellement à calculer aᵇ mod n où a, b et n comptent chacun des centaines de chiffres.
  • Fonctions de hachage : la plupart des schémas de hachage réduisent une entrée de taille arbitraire à un « compartiment » de taille fixe au moyen d'une opération modulo, ce qui explique la présence du mod dans les tables de hachage, les sommes de contrôle et la logique de répartition de charge.
  • Calendriers et horloges : le calcul du jour de la semaine, les conversions d'heure 12/24 et les cycles calendaires sont tous de l'arithmétique modulaire déguisée — le surnom d'« arithmétique de l'horloge » vient directement de là.
  • Les conventions de signe diffèrent : les mathématiques définissent toujours a mod n comme non négatif, mais de nombreux langages de programmation (C, JavaScript, Java) renvoient plutôt un reste ayant le même signe que a, ce qui peut piéger la traduction directe des formules en code.

Questions fréquentes

Que vaut −7 mod 3 ?

Cet outil suit la convention mathématique selon laquelle le résultat est toujours non négatif : −7 mod 3 = 2 (puisque −7 = −3×3 + 2). Certains langages de programmation renvoient −1 à la place, car ils définissent le reste comme ayant le même signe que le dividende plutôt que d'être toujours positif.

Où utilise-t-on aᵇ mod n dans la vie réelle ?

C'est l'opération centrale de l'échange de clés RSA et Diffie-Hellman : chiffrer un message ou convenir d'un secret partagé revient essentiellement à calculer une énorme puissance modulaire, souvent avec des nombres de 2048 bits ou plus.

Pourquoi l'exemple de l'horloge utilise-t-il mod 24 et non mod 12 ?

Les deux fonctionnent — une horloge de 12 heures boucle à mod 12, une horloge de 24 heures à mod 24. Le module n est simplement la taille du cycle qui vous intéresse ; choisissez la convention horaire qui correspond à votre façon de compter le temps.

a mod n est-il la même chose que la division entière ?

Ce sont les deux moitiés d'une même division. a ÷ n (division entière) donne le quotient — combien de fois n entre entièrement dans a — tandis que a mod n donne ce qu'il reste. Ensemble, quotient × n + reste reconstitue toujours a.

Pourquoi l'exponentiation rapide (carré-et-multiplication) est-elle plus rapide que le calcul direct de aᵇ ?

L'exponentiation directe multiplie a par lui-même b−1 fois, et la valeur intermédiaire explose en taille bien avant que vous ne puissiez la réduire modulo n. L'exponentiation rapide réduit au contraire après chaque étape d'élévation au carré, si bien que les nombres impliqués ne dépassent jamais, à peu près, la taille de n — transformant une opération qui prendrait plus de temps que l'âge de l'univers pour des tailles de clés cryptographiques en une opération qui se termine en quelques millisecondes.

Commentaires

Pas encore de commentaires — soyez le premier à en écrire un !

Outils similaires

Calculatrice Calculatrice en ligne gratuite avec prise en charge du clavier : quatre opérations, pourcentages, parenthèses et historique. Lancer Calcul de pourcentage Calculez X % d'un nombre, quel pourcentage un nombre représente d'un autre, et l'augmentation ou la diminution en pourcentage. Lancer Calculateur de PGCD & PPCM Calculez le plus grand commun diviseur et le plus petit commun multiple de deux nombres ou plus, avec les étapes affichées. Lancer Calculateur de combinaisons et permutations Calculez les combinaisons C(n,r), les permutations P(n,r) et la factorielle n! avec des résultats exacts. Lancer