Calculator voor de Chinese reststelling
Tel een stapel dingen per drie en er blijven 2 over, per vijf blijven er 3 over, per zeven blijven er 2 over: het zijn er 23, of 128, of 233, elke 105 een antwoord. Dat is het probleem uit de Sunzi Suanjing dat de Chinese reststelling haar naam gaf. Typ een willekeurig stelsel van congruenties x ≡ a (mod n), met zoveel vergelijkingen en zulke grote getallen als je wilt, en zie het antwoord, de uitwerking met jouw getallen en een afbeelding van waarom het werkt. Als de vergelijkingen niet allemaal kunnen gelden, noemt de calculator de twee die botsen en laat hij zien waarom. Typ de vergelijkingen x ≡ a (mod n), één per rij: a is de rest en n de modulus. Voeg een rij toe met Vergelijking toevoegen, of met Enter in de laatste modulus, en verwijder er een met ×. Gehele getallen tot 200 cijfers werken, en a mag negatief zijn. Of kies een uitgewerkt voorbeeld. De tegels tonen de kleinste oplossing en hoe vaak die terugkomt; daaronder staan de eerste positieve oplossingen en een controle van elke vergelijking. De afbeelding markeert de getallen die aan elke vergelijking voldoen, en de kolom waarin elke rij een markering heeft is de oplossing; de restentabel toont twee vergelijkingen tegelijk. De uitwerking staat er met jouw getallen, via de constructie uit het leerboek of via substitutie.
Hoe het werkt
- Typ de vergelijkingen x ≡ a (mod n), één per rij, of kies een uitgewerkt voorbeeld zoals het probleem van Sunzi, de mand met eieren of de Juliaanse periode.
- Lees de kleinste oplossing af, de modulus waarmee die terugkomt en de eerste positieve oplossingen, elk gecontroleerd tegen elke vergelijking.
- Volg de uitwerking stap voor stap, via de constructie of via substitutie, en schakel de afbeelding tussen de getallenlijn en de restentabel.
Hoe de constructie werkt
Als geen twee moduli een gemeenschappelijke factor hebben, kun je de oplossing direct bouwen. Vermenigvuldig de moduli: voor het probleem van Sunzi is N = 3 × 5 × 7 = 105. Neem voor elke vergelijking Nᵢ = N / nᵢ, een veelvoud van elke andere modulus: 35, 21 en 15. Zoek daarna de inverse yᵢ van Nᵢ mod nᵢ met het uitgebreide algoritme van Euclides: 35 geeft rest 2 bij deling door 3, en 2 × 2 = 4 ≡ 1 (mod 3), dus y₁ = 2; 21 en 15 geven rest 1, dus hun inversen zijn 1. Nu is x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, en 233 mod 105 = 23. Elke term past bij zijn eigen vergelijking en is een veelvoud van de andere moduli, dus de som past bij allemaal.
Als de moduli een factor delen
Ook een stelsel waarvan de moduli factoren delen, kan een oplossing hebben. Twee vergelijkingen x ≡ a (mod m) en x ≡ b (mod n) kunnen precies dan allebei gelden als a − b een veelvoud is van gcd(m, n), en de oplossing herhaalt zich dan elke lcm(m, n) in plaats van elke m × n. Twee bussen die op minuut 5 en 11 vertrekken, elke 12 en elke 18 minuten, treffen elkaar op minuut 29 en daarna elke 36 minuten, omdat 11 − 5 = 6 een veelvoud is van gcd(12, 18) = 6. Maar x ≡ 1 (mod 4) en x ≡ 4 (mod 6) kunnen nooit allebei gelden: de eerste maakt x oneven en de tweede even. Een heel stelsel heeft precies dan een oplossing als elk paar van zijn vergelijkingen er een heeft, en zo vindt de calculator de twee die botsen.
Veelgestelde vragen
Wat zegt de Chinese reststelling?
Als geen twee van de moduli n₁, n₂, … een gemeenschappelijke factor hebben, dan is er voor willekeurige resten a₁, a₂, … precies één x van 0 tot N − 1 met x ≡ aᵢ (mod nᵢ) voor elke i, waarbij N het product van de moduli is. Elke andere oplossing verschilt daarvan een veelvoud van N: bij het probleem van Sunzi zijn de oplossingen 23, 128, 233 enzovoort, elke 105 één.
Waarom heet ze Chinees?
Het oudste bekende probleem van deze soort staat in de Sunzi Suanjing, een Chinees rekenboek uit de 3e tot 5e eeuw: per drie, per vijf en per zeven geteld laat een aantal dingen de resten 2, 3 en 2. Qin Jiushao gaf in 1247 een algemene methode voor zulke problemen, en Carl Friedrich Gauss formuleerde de stelling in 1801 in haar moderne vorm.
En als de moduli niet relatief priem zijn?
Dan is er misschien geen oplossing, en als die er is, herhaalt ze zich elk kleinste gemene veelvoud van de moduli in plaats van elk product. Twee vergelijkingen kloppen met elkaar als hun resten gelijk zijn modulo de gcd van hun moduli. Het eierraadsel gebruikt 2, 3, 4, 5, 6 en 7, die factoren delen, en heeft toch een oplossing: 301, die zich elke 420 herhaalt.
Hoe gebruikt RSA de Chinese reststelling?
Een RSA-bericht ontsleutelen betekent c^d mod n berekenen, met n = p × q. Het is sneller om c^d mod p en c^d mod q apart te berekenen, met de exponent gereduceerd mod p − 1 en q − 1, en de twee uitkomsten met de stelling samen te voegen. Met getallen die half zo lang zijn, kost elk van de twee machten ongeveer een achtste van het werk, dus is ontsleutelen ongeveer vier keer zo snel, en de meeste RSA-software doet het zo.
Hoe groot mogen de getallen zijn?
Tot 20 vergelijkingen, met getallen van elk hoogstens 200 cijfers. De calculator rekent met exacte gehele getallen in je browser, dus het antwoord is exact hoe lang het ook is, en er wordt niets verstuurd.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor