Kalkylator för kinesiska restsatsen
Räkna en hög saker tre åt gången och 2 blir över, fem åt gången blir 3 över, sju åt gången blir 2 över: det är 23, eller 128, eller 233, ett svar för var 105:e tal. Det är problemet ur Sunzi Suanjing som gav kinesiska restsatsen dess namn. Skriv vilket kongruenssystem x ≡ a (mod n) som helst, med så många ekvationer och så stora tal du vill, och se svaret, uträkningen med dina tal och en bild av varför det fungerar. När ekvationerna inte alla kan gälla pekar kalkylatorn ut de två som krockar och visar varför. Skriv ekvationerna x ≡ a (mod n), en per rad: a är resten och n modulen. Lägg till en rad med Lägg till ekvation, eller med Enter i den sista modulen, och ta bort en med ×. Heltal med upp till 200 siffror fungerar, och a får vara negativt. Eller välj ett räkneexempel. Rutorna visar den minsta lösningen och hur ofta den upprepas; under dem står de första positiva lösningarna och en kontroll av varje ekvation. Bilden markerar talen som uppfyller varje ekvation, och kolumnen där varje rad har en markering är lösningen; resttabellen visar två ekvationer på en gång. Uträkningen skrivs ut med dina tal, med lärobokens konstruktion eller med insättning.
Hur det fungerar
- Skriv ekvationerna x ≡ a (mod n), en per rad, eller välj ett räkneexempel som Sunzis problem, äggkorgen eller den julianska perioden.
- Läs av den minsta lösningen, modulen den upprepas med och de första positiva lösningarna, var och en kontrollerad mot varje ekvation.
- Följ uträkningen steg för steg, med konstruktionen eller med insättning, och växla bilden mellan tallinjen och resttabellen.
Så fungerar konstruktionen
När inga två moduler har en gemensam faktor kan lösningen byggas direkt. Multiplicera modulerna: för Sunzis problem är N = 3 × 5 × 7 = 105. Ta för varje ekvation Nᵢ = N / nᵢ, en multipel av varje annan modul: 35, 21 och 15. Hitta sedan inversen yᵢ till Nᵢ mod nᵢ med den utvidgade euklidiska algoritmen: 35 ger resten 2 vid division med 3, och 2 × 2 = 4 ≡ 1 (mod 3), så y₁ = 2; 21 och 15 ger resten 1, så deras inverser är 1. Nu är x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, och 233 mod 105 = 23. Varje term passar sin egen ekvation och är en multipel av de andra modulerna, så summan passar alla.
När modulerna har en gemensam faktor
Även ett system vars moduler har gemensamma faktorer kan ha en lösning. Två ekvationer x ≡ a (mod m) och x ≡ b (mod n) kan gälla samtidigt precis när a − b är en multipel av gcd(m, n), och lösningen upprepas då var lcm(m, n):e tal i stället för var m × n:e. Två bussar som går vid minut 5 och 11, var 12:e och var 18:e minut, möts vid minut 29 och sedan var 36:e minut, eftersom 11 − 5 = 6 är en multipel av gcd(12, 18) = 6. Men x ≡ 1 (mod 4) och x ≡ 4 (mod 6) kan aldrig gälla samtidigt: den första gör x udda och den andra jämnt. Ett helt system har en lösning precis när varje par av dess ekvationer har en, och så hittar kalkylatorn de två som krockar.
Ofta ställda frågor
Vad säger kinesiska restsatsen?
Om inga två av modulerna n₁, n₂, … har en gemensam faktor finns det för godtyckliga rester a₁, a₂, … exakt ett x från 0 till N − 1 med x ≡ aᵢ (mod nᵢ) för varje i, där N är produkten av modulerna. Varje annan lösning skiljer sig från den med en multipel av N: för Sunzis problem är lösningarna 23, 128, 233 och så vidare, en för var 105:e tal.
Varför kallas den kinesisk?
Det äldsta kända problemet av det här slaget finns i Sunzi Suanjing, en kinesisk räknebok skriven mellan 200- och 400-talet: räknade tre, fem och sju åt gången lämnar ett antal saker resterna 2, 3 och 2. Qin Jiushao gav en allmän metod för sådana problem 1247, och Carl Friedrich Gauss formulerade satsen i sin moderna form 1801.
Vad händer om modulerna inte är relativt prima?
Då finns det kanske ingen lösning, och om det finns en upprepas den var minsta gemensamma multipel av modulerna i stället för var produkt. Två ekvationer stämmer överens när deras rester är lika modulo gcd av deras moduler. Äggproblemet använder 2, 3, 4, 5, 6 och 7, som har gemensamma faktorer, och har ändå en lösning: 301, som upprepas var 420:e tal.
Hur använder RSA kinesiska restsatsen?
Att dekryptera ett RSA-meddelande innebär att beräkna c^d mod n, där n = p × q. Det går snabbare att beräkna c^d mod p och c^d mod q var för sig, med exponenten reducerad mod p − 1 och q − 1, och sätta ihop de två resultaten med satsen. Med tal som är hälften så långa kostar var och en av de två potenserna ungefär en åttondel av arbetet, så dekrypteringen går ungefär fyra gånger snabbare, och det mesta RSA-program gör så.
Hur stora får talen vara?
Upp till 20 ekvationer, med tal på upp till 200 siffror var. Kalkylatorn räknar med exakta heltal i din webbläsare, så svaret är exakt hur långt det än är, och inget skickas någonstans.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor