Calculateur du théorème des restes chinois (TRC) — Résoudre des congruences simultanées
Résout un système de congruences simultanées x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... grâce au théorème des restes chinois. Vérifie automatiquement que les modules sont premiers entre eux deux à deux et fournit la plus petite solution non négative ainsi que la solution générale.
Exemple résolu : le problème du « nombre inconnu » du Sunzi Suanjing
Un problème classique tiré du Sunzi Suanjing (le « classique mathématique de Sun Tzu »), un traité d'arithmétique chinois datant approximativement du IIIe au Ve siècle, souvent cité comme l'origine du théorème des restes chinois. La question « quel nombre laisse un reste de 2 divisé par 3, un reste de 3 divisé par 5 et un reste de 2 divisé par 7 ? » a pour réponse 23, modulo 105.
| Condition 1 | x ≡ 2 (mod 3) |
|---|---|
| Condition 2 | x ≡ 3 (mod 5) |
| Condition 3 | x ≡ 2 (mod 7) |
| Solution | x ≡ 23 (mod 105) |
Astuces
- Si les modules (nᵢ) ne sont pas premiers entre eux deux à deux, une erreur s'affiche — par exemple mod 4 et mod 6 partagent le facteur 2, donc ce calculateur ne peut pas résoudre ce système (il faudrait le TRC généralisé).
- Inutile de réduire vous-même le reste aᵢ : même s'il est négatif ou supérieur à nᵢ, le calculateur le normalise automatiquement en mod nᵢ en interne avant de résoudre.
- Vous pouvez ajouter de 2 à 5 congruences. Pratique pour les énigmes exigeant qu'un nombre satisfasse trois conditions périodiques ou plus à la fois, comme le célèbre problème « deviner le nombre de soldats ».
- La solution générale est affichée sous la forme x ≡ résultat (mod N) : ajouter n'importe quel multiple de N au résultat satisfait toujours toutes les congruences d'origine.
Questions fréquentes
Anecdote — D'un traité d'arithmétique du IIIe siècle à l'accélération du chiffrement RSA
Le théorème des restes chinois remonte à un problème du Sunzi Suanjing, un classique arithmétique chinois que l'on situe généralement entre le IIIe et le Ve siècle de notre ère. Sa célèbre énigme du « nombre inconnu » — trouver un nombre laissant des restes de 2, 3 et 2 lorsqu'il est divisé respectivement par 3, 5 et 7 — capturait déjà l'idée essentielle du théorème moderne : reconstituer un nombre inconnu à partir de plusieurs restes de division.
L'une des applications pratiques les plus importantes du théorème des restes chinois aujourd'hui est l'accélération du déchiffrement RSA. Le déchiffrement RSA nécessite d'élever un grand nombre à une puissance modulo un nombre composé n = p × q, où p et q sont de grands nombres premiers. Plutôt que de travailler directement modulo n, le TRC permet d'effectuer le calcul indépendamment modulo p et modulo q, puis de recombiner les résultats — une technique appelée CRT-RSA qui peut théoriquement accélérer le déchiffrement de près de quatre fois, et qui est implémentée dans de nombreuses bibliothèques cryptographiques.
Cet outil prend en charge la forme classique du théorème, qui exige que tous les modules soient premiers entre eux deux à deux. Lorsque les modules partagent des facteurs communs (par exemple mod 4 et mod 6), une solution peut parfois encore exister, mais sa détermination nécessite le théorème des restes chinois généralisé, ce qui dépasse le cadre de cet outil.