Arithmétique modulaire - Modular arithmetic

Le chronométrage sur cette horloge utilise l'arithmétique modulo 12.

En mathématiques , l'arithmétique modulaire est un système d' arithmétique pour les entiers , où les nombres "s'enroulent" lorsqu'ils atteignent une certaine valeur, appelée module . L'approche moderne de l'arithmétique modulaire a été développée par Carl Friedrich Gauss dans son livre Disquisitiones Arithmeticae , publié en 1801.

Une utilisation familière de l'arithmétique modulaire est l' horloge de 12 heures , dans laquelle la journée est divisée en deux périodes de 12 heures. S'il est 7h00 maintenant, 8 heures plus tard, il sera 3h00. Une simple addition donnerait 7 + 8 = 15 , mais les horloges "tournent" toutes les 12 heures. Étant donné que le nombre d'heures recommence après avoir atteint 12, il s'agit de l'arithmétique modulo 12. En termes de définition ci-dessous, 15 est congru à 3 modulo 12, donc "15:00" sur une horloge de 24 heures est affiché "3:00 " sur une horloge de 12 heures.

Congruence

Étant donné un entier n > 1 , appelé module , deux entiers a et b sont dits congrus modulo n , si n est un diviseur de leur différence (c'est-à-dire s'il existe un entier k tel que ab = kn ).

La congruence modulo n est une relation de congruence , c'est-à-dire une relation d'équivalence compatible avec les opérations d' addition , de soustraction et de multiplication . La congruence modulo n est notée :

Les parenthèses signifient que (mod n ) s'applique à l'ensemble de l'équation, pas seulement au membre de droite (ici b ). Cette notation n'est pas à confondre avec la notation b mod n (sans parenthèses), qui fait référence à l' opération modulo . En effet, b mod n désigne l'entier unique a tel que 0 a < n et (ie, le reste de lorsqu'il est divisé par ).

La relation de congruence peut être réécrite comme

montrant explicitement sa relation avec la division euclidienne . Cependant, le b ici n'a pas besoin d'être le reste de la division de a par n . Au lieu de cela, ce que l'énoncé ab (mod n ) affirme, c'est que a et b ont le même reste lorsqu'ils sont divisés par n . C'est-à-dire,

0 r < n est le reste commun. En soustrayant ces deux expressions, on retrouve la relation précédente :

en fixant k = pq .

Exemples

Dans le module 12, on peut affirmer que :

parce que 38 − 14 = 24 , qui est un multiple de 12. Une autre façon d'exprimer cela est de dire que 38 et 14 ont le même reste 2, lorsqu'ils sont divisés par 12.

La définition de la congruence s'applique également aux valeurs négatives. Par exemple:


Propriétés

La relation de congruence satisfait toutes les conditions d'une relation d'équivalence :

  • Réflexivité : aa (mod n )
  • Symmetry: unb (mod n ) si ba (mod n ) pour tout un , b et n .
  • Transitivité : Si ab (mod n ) et bc (mod n ) , alors ac (mod n )

Si a 1b 1 (mod n ) et a 2b 2 (mod n ), ou si ab (mod n ), alors :

  • a + kb + k (mod n ) pour tout entier k (compatibilité avec traduction)
  • kakb (mod n ) pour tout entier k (compatibilité avec la mise à l'échelle)
  • a 1 + a 2b 1 + b 2 (mod n ) (compatibilité avec addition)
  • a 1a 2b 1b 2 (mod n ) (compatibilité avec soustraction)
  • a 1 a 2b 1 b 2 (mod n ) (compatibilité avec multiplication)
  • a kb k (mod n ) pour tout entier k non négatif(compatibilité avec l'exponentiation)
  • p ( a ) ≡ p ( b ) (mod n ) , pour tout polynôme p ( x ) à coefficients entiers (compatibilité avec évaluation polynomiale)

Si unb (mod n ) , alors il est généralement faux que k unk b (mod n ) . Cependant, ce qui suit est vrai :

Pour l'annulation des termes communs, nous avons les règles suivantes:

  • Si un + kb + k (mod n ) , où k est un entier quelconque, puis unb (mod n )
  • Si kakb (mod n ) et k est premier avec n , alors ab (mod n )
  • Si kakb (mod kn ) , alors ab (mod n )

L' inverse multiplicatif modulaire est défini par les règles suivantes :

  • Existence : il existe un entier noté a –1 tel que aa –1 1 (mod n ) si et seulement si a est premier avec n . Cet entier a –1 est appelé un inverse multiplicatif modulaire de a modulo n .
  • Si ab (mod n ) et a –1 existe, alors a –1b –1 (mod n ) (compatibilité avec inverse multiplicatif, et, si a = b , unicité modulo n )
  • Si axb (mod n ) et un est premier avec n , alors la solution à cette congruence linéaire est donnée par xa -1 b (mod n )

L'inverse multiplicatif xa -1 (mod n ) peut être efficacement calculée en résolvant l'équation de Bezout pour -en utilisant l' algorithme d' Euclide étendu .

En particulier, si p est un nombre premier, alors a est premier avec p pour tout a tel que 0 < a < p ; ainsi un inverse multiplicatif existe pour tout a qui n'est pas congru à zéro modulo p .

Certaines des propriétés les plus avancées des relations de congruence sont les suivantes :

  • Petit théorème de Fermat : Si p est premier et ne divise pas a , alors a p – 1 1 (mod p ) .
  • Théorème d'Euler : Si a et n sont premiers entre eux, alors a φ ( n ) ≡ 1 (mod n ) , où φ est la fonction totale d'Euler
  • Une conséquence simple du petit théorème de Fermat est que si p est premier, alors a −1a p − 2 (mod p ) est l'inverse multiplicatif de 0 < a < p . Plus généralement, d'après le théorème d'Euler, si a et n sont premiers entre eux, alors a −1a φ ( n ) − 1 (mod n ) .
  • Une autre conséquence simple est que si unb (mod φ ( n )),φ est la fonction indicatrice d'Euler, puis k unk b (mod n ) fourni k est coprime avec n .
  • Théorème de Wilson : p est premier si et seulement si ( p − 1) ! -1 (mod p ) .
  • Théorème chinois : Pour tout a , b et coprime m , n , il existe un cadre unique x (mod mn ) tel que xa (mod m ) et xb (mod n ) . En fait, xbm n –1 m + an m –1 n (mod mn )m n −1 est l'inverse de m modulo n et n m −1 est l'inverse de n modulo m .
  • Théorème de Lagrange : La congruence f ( x ) 0 (mod p ) , où p est premier, et f ( x ) = a 0 x n + ... + a n est un polynôme à coefficients entiers tel que a 0 0 (mod p ) , a au plus n racines.
  • Racine primitive modulo n : un nombre g est une racine primitive modulo N si, pour tout entier d' un premier avec n , il existe un entier k tel que g ka (mod n ) . Une racine primitive modulo n existe si et seulement si n est égal à 2, 4, p k ou 2 p k , où p est un nombre premier impair et k est un entier positif. Si un modulo racine primitive n existe, alors il y a exactement φ ( φ ( n )) telles racines primitives, où φ est la fonction indicatrice d'Euler.
  • Résidu quadratique : Entier un est un résidu quadratique modulo n , s'il existe un entier x tel que x 2a (mod n ) . Le critère d'Euler affirme que, si p est un nombre premier impair, et a n'est pas un multiple de p , alors a est un résidu quadratique modulo p si et seulement si

Cours de congruence

Comme toute relation de congruence, la congruence modulo n est une relation d'équivalence , et la classe d'équivalence de l'entier a , notée a n , est l'ensemble {… , a − 2 n , an , a , a + n , a + 2 n , …} . Cet ensemble, constitué de tous les nombres entiers congru à un  modulo  n , est appelée la classe de congruence , classe résidu , ou tout simplement résidu de l'entier d' un modulo  n . Lorsque le module n est connu du contexte, ce résidu peut également être noté [ a ] .

Systèmes de résidus

Chaque classe de résidus modulo n peut être représentée par n'importe lequel de ses membres, bien que nous représentions habituellement chaque classe de résidus par le plus petit entier non négatif qui appartient à cette classe (puisque c'est le reste propre qui résulte de la division). Deux membres quelconques de classes de résidus différentes modulo n sont incongrus modulo n . De plus, tout entier appartient à une et une seule classe de résidus modulo n .

L'ensemble des entiers {0, 1, 2, …, n − 1} est appelé le système des moindres résidus modulo n . Tout ensemble de n entiers, dont aucun n'est congruent modulo n , est appelé un système résiduel complet modulo n .

Le système au moindre résidu est un système de résidus complet, et un système de résidus complet est simplement un ensemble contenant précisément un représentant de chaque classe de résidus modulo n . Par exemple. le système au moindre résidu modulo 4 est {0, 1, 2, 3}. Certains autres systèmes de résidus complets modulo 4 comprennent :

  • {1, 2, 3, 4}
  • {13, 14, 15, 16}
  • {-2, -1, 0, 1}
  • {−13, 4, 17, 18}
  • {-5, 0, 6, 21}
  • {27, 32, 37, 42}

Certains ensembles qui ne sont pas des systèmes de résidus complets modulo 4 sont :

  • {−5, 0, 6, 22}, puisque 6 est congru à 22 modulo 4.
  • {5, 15}, puisqu'un système de résidus complet modulo 4 doit avoir exactement 4 classes de résidus incongrues.

Systèmes à résidus réduits

Étant donné la fonction totient d'Euler φ( n ) , tout ensemble d' entiers φ( n ) qui sont relativement premiers à n et mutuellement incongrus sous le module n est appelé un système de résidus réduit modulo n . L'ensemble {5,15} ci-dessus, par exemple, est une instance d'un système de résidus réduit modulo 4.

Entiers modulo n

L'ensemble de toutes les classes de congruence des entiers pour un module n est appelé anneau des entiers modulo n , et est désignée , ou . La notation est cependant déconseillée car elle peut être confondue avec l'ensemble des entiers n- adiques . L'anneau est fondamental pour diverses branches des mathématiques (voir § Applications ci-dessous).

L'ensemble est défini pour n > 0 comme :

(Lorsque n = 0 , n'est pas un ensemble vide ; il est plutôt isomorphe à , puisque a 0 = { a } .)

Nous définissons l'addition, la soustraction et la multiplication par les règles suivantes :

La vérification qu'il s'agit d'une définition correcte utilise les propriétés données précédemment.

De cette façon, devient un anneau commutatif . Par exemple, dans l'anneau , nous avons

comme dans l'arithmétique pour l'horloge de 24 heures.

Nous utilisons la notation car il s'agit de l' anneau quotient de par l' idéal , un ensemble contenant tous les entiers divisibles par n , où est l' ensemble singleton {0} . Ainsi est un champ quand est un idéal maximal (c'est-à-dire quand n est premier).

Celui-ci peut également être construit à partir du groupe sous l'opération d'addition seule. La classe de résidus a n est le groupe coset de a dans le groupe quotient , un groupe cyclique .

Plutôt que d'exclure le cas particulier n = 0 , il est plus utile d'inclure (qui, comme mentionné précédemment, est isomorphe à l'anneau des entiers). En fait, cette inclusion est utile lorsque l'on discute de la caractéristique d'un anneau .

L'anneau d'entiers modulo n est un corps fini si et seulement si n est premier (cela garantit que tout élément non nul a un inverse multiplicatif ). Si est une puissance première avec k > 1, il existe un corps fini unique (à isomorphisme près) avec n éléments, mais ce n'est pas , qui n'est pas un corps car il a des diviseurs nuls .

Le sous - groupe multiplicatif d'entiers modulo n est noté . Cela consiste en (où a est premier à n ), qui sont précisément les classes possédant un inverse multiplicatif. Cela forme un groupe commutatif par multiplication, d'ordre .

Applications

En mathématiques théoriques, l'arithmétique modulaire est l'un des fondements de la théorie des nombres , touchant presque tous les aspects de son étude, et elle est également largement utilisée dans la théorie des groupes , la théorie des anneaux , la théorie des nœuds et l'algèbre abstraite . En mathématiques appliquées, il est utilisé en algèbre informatique , en cryptographie , en informatique , en chimie et dans les arts visuels et musicaux .

Une application très pratique consiste à calculer des sommes de contrôle au sein d'identifiants de numéros de série. Par exemple, l' International Standard Book Number (ISBN) utilise l'arithmétique modulo 11 (pour l'ISBN à 10 chiffres) ou modulo 10 (pour l'ISBN à 13 chiffres) pour la détection des erreurs. De même, les numéros de compte bancaire international (IBAN), par exemple, utilisent l'arithmétique modulo 97 pour repérer les erreurs de saisie par l'utilisateur dans les numéros de compte bancaire. En chimie, le dernier chiffre du numéro de registre CAS (un numéro d'identification unique pour chaque composé chimique) est un chiffre de contrôle , qui est calculé en prenant le dernier chiffre des deux premières parties du numéro de registre CAS multiplié par 1, le chiffre précédent fois 2, le chiffre précédent fois 3 etc., en additionnant tout cela et en calculant la somme modulo 10.

En cryptographie, l'arithmétique modulaire sous-tend directement les systèmes à clé publique tels que RSA et Diffie-Hellman , et fournit des champs finis qui sous-tendent les courbes elliptiques , et est utilisé dans une variété d' algorithmes à clé symétrique, y compris Advanced Encryption Standard (AES), International Data Encryption Algorithm ( IDÉE), et RC4 . RSA et Diffie–Hellman utilisent l'exponentiation modulaire .

En calcul formel, l'arithmétique modulaire est couramment utilisée pour limiter la taille des coefficients entiers dans les calculs et les données intermédiaires. Il est utilisé dans la factorisation polynomiale , un problème pour lequel tous les algorithmes efficaces connus utilisent l'arithmétique modulaire. Il est utilisé par les implémentations les plus efficaces des algorithmes du plus grand commun diviseur polynomial , de l'algèbre linéaire exacte et de la base de Gröbner sur les entiers et les nombres rationnels. Comme publié sur Fidonet dans les années 1980 et archivé à Rosetta Code , l'arithmétique modulaire a été utilisée pour réfuter la conjecture de la somme des puissances d'Euler sur un micro-ordinateur Sinclair QL en utilisant seulement un quart de la précision entière utilisée par un supercalculateur CDC 6600 pour la réfuter deux décennies plus tôt via une recherche par force brute .

En informatique, l'arithmétique modulaire est souvent appliquée dans les opérations au niveau du bit et d'autres opérations impliquant des structures de données cycliques à largeur fixe . L' opération modulo , telle qu'elle est implémentée dans de nombreux langages de programmation et calculatrices , est une application de l'arithmétique modulaire qui est souvent utilisée dans ce contexte. L'opérateur logique XOR additionne 2 bits, modulo 2.

En musique, l'arithmétique modulo 12 est utilisée dans l'examen du système de tempérament égal à douze tons , où l' équivalence d' octave et d' enharmonique se produit (c'est-à-dire que les hauteurs dans un rapport 1∶2 ou 2∶1 sont équivalentes, et Do dièse est considéré comme le même que D- flat ).

La méthode de lancement des neufs offre une vérification rapide des calculs arithmétiques décimaux effectués à la main. Elle est basée sur l'arithmétique modulaire modulo 9, et plus précisément sur la propriété cruciale que 10 1 (mod 9).

L'arithmétique modulo 7 est utilisée dans les algorithmes qui déterminent le jour de la semaine pour une date donnée. En particulier, la congruence de Zeller et l' algorithme Doomsday font un usage intensif de l'arithmétique modulo-7.

Plus généralement, l'arithmétique modulaire a également des applications dans des disciplines telles que le droit (par exemple, la répartition ), l' économie (par exemple, la théorie des jeux ) et d'autres domaines des sciences sociales , où la division proportionnelle et l'allocation des ressources joue un rôle central dans l'analyse.

Complexité de calcul

Étant donné que l'arithmétique modulaire a un si large éventail d'applications, il est important de savoir à quel point il est difficile de résoudre un système de congruences. Un système linéaire de congruences peut être résolu en temps polynomial avec une forme d' élimination gaussienne , pour plus de détails voir le théorème de congruence linéaire . Des algorithmes, tels que la réduction de Montgomery , existent également pour permettre à des opérations arithmétiques simples, telles que la multiplication et l' exponentiation modulo  n , d'être exécutées efficacement sur de grands nombres.

Certaines opérations, comme trouver un logarithme discret ou une congruence quadratique, semblent être aussi difficiles que la factorisation d'entiers et constituent donc un point de départ pour les algorithmes cryptographiques et le chiffrement . Ces problèmes peuvent être NP-intermédiaire .

La résolution d'un système d'équations arithmétiques modulaires non linéaires est NP-complet .

Exemples d'implémentations

Vous trouverez ci-dessous trois fonctions C raisonnablement rapides, deux pour effectuer une multiplication modulaire et une pour une exponentiation modulaire sur des entiers non signés ne dépassant pas 63 bits, sans débordement des opérations transitoires.

Une façon algorithmique de calculer :

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   if (!((a | b) & (0xFFFFFFFFULL << 32)))
       return a * b % m;

   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d >= m) d -= m;
       a <<= 1;
   }
   return d;
}

Sur les architectures informatiques où un format de précision étendu avec au moins 64 bits de mantisse est disponible (comme le type long double de la plupart des compilateurs x86 C), la routine suivante est, en employant l'astuce qui, par le matériel, les résultats de multiplication à virgule flottante dans les bits les plus significatifs du produit conservé, tandis que la multiplication d'entiers donne les bits les moins significatifs conservés :

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   long double x;
   uint64_t c;
   int64_t r;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Vous trouverez ci-dessous une fonction C pour effectuer une exponentiation modulaire, qui utilise la fonction mul_mod implémentée ci-dessus.

Une façon algorithmique de calculer :

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t r = m==1?0:1;
    while (b > 0) {
        if (b & 1)
            r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}

Cependant, pour que toutes les routines ci-dessus fonctionnent, m ne doit pas dépasser 63 bits.

Voir également

Remarques

Les références

Liens externes