En mathématiques, l'arithmétique modulaire est un système de calcul pour les nombres entiers, à l'aide duquel ils "se retournent" lorsqu'ils atteignent une certaine valeur - le module (ou le pluriel d'entre eux). L'approche moderne de ce type de science a été développée par Carl Friedrich Gauss dans ses Disquisitiones Arithmeticae publiées en 1801. Les informaticiens aiment beaucoup utiliser cette méthode, car elle est très intéressante et ouvre certaines possibilités nouvelles dans les opérations avec les nombres.
Essence
Parce que le nombre d'heures recommence après avoir atteint 12, c'est arithmétique modulo 12. Selon la définition ci-dessous, 12 correspond non seulement à 12, mais aussi à 0, donc on peut aussi nommer le temps appelé " 12:00". "0:00". Après tout, 12 est égal à 0 modulo 12.
L'arithmétique modulaire peut être traitée mathématiquement en introduisant une relation congruente aux nombres entiers qui est compatible avec les opérations sur les nombres entiersnombres: addition, soustraction et multiplication. Pour un entier positif n, deux nombres a et b sont dits congruents modulo n si leur différence a - b est un multiple de n (c'est-à-dire s'il existe un entier k tel que a - b=kn).
Déductions
En mathématiques théoriques, l'arithmétique modulaire est l'un des fondements de la théorie des nombres, affectant presque tous les aspects de son étude, et est également largement utilisée dans la théorie des groupes, des anneaux, des nœuds et de l'algèbre abstraite. Dans le domaine des mathématiques appliquées, il est utilisé dans le calcul formel, la cryptographie, l'informatique, la chimie, les arts visuels et la musique.
Pratique
Une application très pratique est le calcul des sommes de contrôle dans les identificateurs de numéros de série. Par exemple, certaines normes de livre courantes utilisent l'arithmétique modulo 11 (si publié avant le 1er janvier 2007) ou modulo 10 (si publié avant ou après le 1er janvier 2007). De même, par exemple, dans les numéros de compte bancaire international (IBAN). Cela utilise l'arithmétique modulo 97 pour détecter les erreurs de saisie de l'utilisateur dans les numéros de compte bancaire.
En chimie, le dernier chiffre du numéro d'enregistrement CAS (le numéro d'identification unique pour chaque composé chimique) est le chiffre de contrôle. Il est calculé en prenant le dernier chiffre des deux premières parties du numéro d'enregistrement CAS multiplié par 1, le chiffre précédent 2 fois, le chiffre précédent 3 fois, etc., en additionnant le tout et en calculant la somme modulo 10.
Qu'est-ce que la cryptographie ? Le fait est queil a un lien très fort avec le sujet en discussion. En cryptographie, les lois de l'arithmétique modulaire sous-tendent directement les systèmes à clé publique tels que RSA et Diffie-Hellman. Ici, il fournit les champs finis qui sous-tendent les courbes elliptiques. Utilisé dans divers algorithmes à clé symétrique, notamment Advanced Encryption Standard (AES), International Data Encryption Algorithm et RC4.
Demande
Cette méthode est utilisée dans les zones où vous devez lire des nombres. Il a été développé par des mathématiciens, et tout le monde l'utilise, en particulier les informaticiens. Ceci est bien documenté dans des livres comme Modular Arithmetic for Dummies. Cependant, un certain nombre d'experts recommandent de ne pas prendre cette littérature au sérieux.
En informatique, l'arithmétique modulaire est souvent utilisée dans les opérations au niveau du bit et autres impliquant des structures de données circulaires à largeur fixe. Les analystes adorent l'utiliser. L'opération modulo est implémentée dans de nombreux langages de programmation et calculatrices. Dans ce cas, il s'agit d'un exemple d'une telle application. La comparaison modulo, la division avec un reste et d'autres astuces sont également utilisées en programmation.
En musique, l'arithmétique modulo 12 est utilisée lorsqu'on considère un système de tempérament égal de douze tons, dans lequel l'octave et l'enharmonique sont équivalentes. En d'autres termes, les clés dans le rapport 1-2 ou 2-1 sont équivalentes. En musique et dans d'autres sciences humaines, l'arithmétique joue un rôle assez important, mais dans les manuelsles informaticiens n'écrivent généralement pas à ce sujet.
Méthode de réduction des neufs
La méthode de conversion 9s offre une vérification rapide des calculs arithmétiques décimaux manuels. Elle est basée sur l'arithmétique modulaire modulo 9 et en particulier sur la propriété décisive 10 10 1.
il y a d'autres exemples. L'arithmétique modulo 7 est utilisée dans les algorithmes qui déterminent le jour de la semaine pour une date particulière. En particulier, la congruence de Zeller et l'algorithme Doomsday font un usage intensif de l'arithmétique modulo 7.
Autres applications
On a déjà parlé de l'arithmétique modulaire en cryptographie. Dans ce domaine, elle est tout simplement irremplaçable. Plus généralement, l'arithmétique modulaire trouve également des applications dans des disciplines telles que le droit, l'économie (comme la théorie des jeux) et d'autres domaines des sciences sociales. En d'autres termes, où la division et la distribution proportionnelles des ressources jouent un rôle majeur.
Parce que l'arithmétique modulaire a un si large éventail d'utilisations, il est important de savoir à quel point il est difficile de résoudre un système de comparaisons. Un système linéaire de congruences peut être résolu en temps polynomial sous la forme d'une élimination gaussienne. Ceci est décrit plus en détail par le théorème de congruence linéaire. Des algorithmes tels que la réduction de Montgomery existent également pour permettre d'effectuer efficacement des opérations arithmétiques simples. Par exemple, multiplication et exponentiation modulo n, pour les grands nombres. C'est très important à savoir pour comprendre ce quecryptographie. Après tout, cela ne fonctionne qu'avec des opérations similaires.
Congruence
Certaines opérations, telles que trouver le logarithme discret ou la congruence quadratique, semblent être aussi complexes que la factorisation d'entiers et sont donc le point de départ des algorithmes cryptographiques et du chiffrement. Ces problèmes peuvent être NP-intermédiaires.
Exemples
Voici trois fonctions C assez rapides - deux pour effectuer une multiplication modulaire et une pour élever à des nombres modulaires pour des entiers non signés jusqu'à 63 bits, sans débordement transitoire.
Peu de temps après la découverte des nombres entiers (1, 2, 3, 4, 5…) il devient évident qu'ils sont divisés en deux groupes:
- Pair: divisible par 2 (0, 2, 4, 6..).
- Impair: non divisible par 2 (1, 3, 5, 7…).
Pourquoi cette distinction est-elle importante ? C'est le début de l'abstraction. Nous remarquons les propriétés du nombre (par exemple, pair ou impair) et pas seulement le nombre lui-même ("37").
Cela nous permet d'explorer les mathématiques à un niveau plus profond et de trouver des relations entre les types de nombres plutôt que des relations spécifiques.
Propriétés d'un nombre
Être un "trois" n'est qu'une autre propriété d'un nombre. Peut-être pas aussi immédiatement utile que pair/impair, mais c'est là. Nous pouvons créer des règles comme "treize x trois veines=treize" et ainsi de suite. Mais c'est fou. Nous ne pouvons pas créer de nouveaux mots tout le temps.
L'opération modulo (mod abrégé ou "%" dans de nombreux langages de programmation) est le reste lorsquedivision. Par exemple, "5 mod 3=2", ce qui signifie que 2 est le reste lorsque vous divisez 5 par 3.
Lors de la conversion de termes usuels en mathématiques, un "nombre pair" correspond à "0 mod 2", ce qui signifie que le reste est 0 lorsqu'il est divisé par 2. Un nombre impair est "1 mod 2" (a un reste de 1).
Nombres pairs et impairs
Qu'est-ce que pair x pair x impair x impair ? Eh bien, c'est 0 x 0 x 1 x 1=0. En fait, vous pouvez voir si un nombre pair est multiplié n'importe où, où le résultat total sera zéro.
L'astuce avec les mathématiques modulaires est que nous les avons déjà utilisées pour stocker l'heure - parfois appelée "arithmétique d'horloge".
Par exemple: 7h00 (am/pm - peu importe). Où sera l'aiguille des heures dans 7 heures ?
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 est le reste quand 14 est divisé par 12. Équation 14 mod 12=2 mod 12 signifie 14 heures et 2 heures regarde le même sur une horloge de 12 heures. Ils sont congruents, indiqués par un triple signe égal: 14 ≡ 2 mod 12.
Autre exemple: il est 8h00. Où sera la grosse main dans 25 heures ?
Au lieu d'ajouter 25 à 8 heures, vous pouvez comprendre que 25 heures correspondent à "1 jour + 1 heure". La réponse est simple. Ainsi, l'horloge se terminera 1 heure plus tôt - à 9h00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Vous avez intuitivement converti 25 en 1 et ajouté ceci à 8.
En utilisant l'horloge comme analogie, nous pouvons déterminer si leles règles de l'arithmétique modulaire, et elles fonctionnent.
Addition/Soustraction
Disons que deux heures se ressemblent sur notre horloge ("2:00" et "14:00"). Si nous ajoutons les mêmes x heures aux deux, que se passe-t-il ? Eh bien, ils changent pour le même montant sur l'horloge! 2:00 + 5 heures ≡ 14:00 + 5 heures - les deux afficheront 7:00.
Pourquoi ? Nous pouvons simplement ajouter 5 aux 2 restes que les deux ont et ils avancent de la même manière. Pour tous les nombres congruents (2 et 14), l'addition et la soustraction ont le même résultat.
Il est plus difficile de savoir si la multiplication reste la même. Si 14 ≡ 2 (mod 12), peut-on multiplier les deux nombres et obtenir le même résultat ? Voyons ce qui se passe lorsque nous multiplions par 3.
Eh bien, 2:003 × 6:00. Mais qu'est-ce que 14h003 ?
Souvenez-vous, 14=12 + 2. Nous pouvons donc dire
143=(12 + 2)3=(123) + (23)
La première partie (123) peut être ignorée ! Le débordement de 12 heures qui en emporte 14 se répète simplement plusieurs fois. Mais qui s'en soucie ? Nous ignorons le débordement de toute façon.
Multiplication
Lors de la multiplication, seul le reste compte, c'est-à-dire les mêmes 2 heures pour 14h00 et 2h00. Intuitivement, c'est ainsi que je vois la multiplication ne pas changer la relation avec les mathématiques modulaires (vous pouvez multiplier les deux côtés d'une relation modulaire et obtenir le même résultat).
Nous le faisons intuitivement, mais c'est bien de lui donner un nom. Vous avez un vol arrivant à 15h00. Ilretardé de 14 heures. À quelle heure atterrira-t-il ?
14 ≡ 2 mod 12. Donc, pensez-y comme 2 heures, donc l'avion atterrira à 5 heures du matin. La solution est simple: 3 + 2=5 heures du matin. C'est un peu plus compliqué que la simple opération modulo, mais le principe est le même.
