Modular Arithmetic

L'arithmétique modulaire prend les restes après les opérations entières, en gardant les résultats dans [0, n) ; c'est le fondement de la théorie des nombres et de la cryptographie.

Objectif

Maintenir les opérations fermées dans un intervalle fini, base de RSA, Diffie-Hellman et d'autres cryptosystèmes.

Mécanisme

(a + b) mod n et (a × b) mod n sont définis modulo n. L'inverse modulaire a^(-1) satisfait a·a^(-1) ≡ 1 (mod n) ; il existe lorsque gcd(a,n)=1 et se calcule avec l'algorithme d'Euclide étendu. D'après le petit théorème de Fermat, a^(p-1) ≡ 1 (mod p) pour p premier.

Cas d’usage

Chiffrement et déchiffrement RSA
Échange de clés Diffie-Hellman
Sharding par modulo de hachage
Calcul de sommes de contrôle

Exemples

entrée
```
(7 + 8) mod 5
```
Output
```
0
```
15 mod 5 = 0

Erreurs courantes

Negative modulo behaves differently across languages: Know your language's behavior or normalize with ((a%n)+n)%n

Termes associés

BigInteger est un type d'entier à précision arbitraire, non limité par une taille de mot fixe, utilisé pour des calculs au-delà de la plage des entiers natifs (comme la cryptographie et la combinatoire).

Un nombre premier est un entier naturel supérieur à 1 divisible uniquement par 1 et par lui-même ; c'est la brique élémentaire de la théorie des nombres, et tout entier se décompose de façon unique en facteurs premiers.

Le PGCD (plus grand commun diviseur) est le plus grand entier positif qui divise deux entiers ou plus, calculé efficacement par l'algorithme d'Euclide.

Outils associés

Calculatrice de précision

High-precision arithmetic calculator. No floating-point errors. Gratuit, privé, 100% côté client.

References