Lommeregner til den kinesiske restklassesætning
Tæl en bunke ting tre ad gangen, og der er 2 tilbage, fem ad gangen 3 tilbage, syv ad gangen 2 tilbage: der er 23, eller 128, eller 233, ét svar for hver 105. Det er opgaven fra Sunzi Suanjing, der gav den kinesiske restklassesætning dens navn. Skriv et vilkårligt kongruenssystem x ≡ a (mod n), med så mange ligninger og så store tal, du vil, og se svaret, udregningen med dine tal og et billede af, hvorfor det virker. Når ligningerne ikke alle kan gælde, nævner lommeregneren de to, der støder sammen, og viser hvorfor. Skriv ligningerne x ≡ a (mod n), én pr. række: a er resten og n modulus. Tilføj en række med Tilføj ligning, eller med Enter i det sidste modulus, og fjern en med ×. Heltal med op til 200 cifre virker, og a må være negativ. Eller vælg et regneeksempel. Felterne viser den mindste løsning, og hvor ofte den gentages; nedenunder står de første positive løsninger og en kontrol af hver ligning. Billedet markerer de tal, der opfylder hver ligning, og den kolonne, hvor hver række har en markering, er løsningen; resttabellen viser to ligninger på én gang. Udregningen står med dine tal, via lærebogens konstruktion eller via indsættelse.
Sådan virker det
- Skriv ligningerne x ≡ a (mod n), én pr. række, eller vælg et regneeksempel som Sunzis opgave, kurven med æg eller den julianske periode.
- Aflæs den mindste løsning, det modulus, den gentages med, og de første positive løsninger, hver kontrolleret mod hver ligning.
- Følg udregningen trin for trin, via konstruktionen eller via indsættelse, og skift billedet mellem tallinjen og resttabellen.
Sådan virker konstruktionen
Når ingen to moduli har en fælles faktor, kan løsningen bygges direkte. Gang moduli sammen: for Sunzis opgave er N = 3 × 5 × 7 = 105. Tag for hver ligning Nᵢ = N / nᵢ, et multiplum af hvert andet modulus: 35, 21 og 15. Find derefter den inverse yᵢ af Nᵢ mod nᵢ med den udvidede euklidiske algoritme: 35 giver rest 2 ved division med 3, og 2 × 2 = 4 ≡ 1 (mod 3), så y₁ = 2; 21 og 15 giver rest 1, så deres inverse er 1. Nu er x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, og 233 mod 105 = 23. Hvert led passer til sin egen ligning og er et multiplum af de andre moduli, så summen passer til dem alle.
Når moduli har en fælles faktor
Også et system, hvis moduli har fælles faktorer, kan have en løsning. To ligninger x ≡ a (mod m) og x ≡ b (mod n) kan gælde samtidig netop når a − b er et multiplum af gcd(m, n), og løsningen gentages så for hvert lcm(m, n) i stedet for hvert m × n. To busser, der kører i minut 5 og 11, hvert 12. og hvert 18. minut, mødes i minut 29 og derefter hvert 36. minut, fordi 11 − 5 = 6 er et multiplum af gcd(12, 18) = 6. Men x ≡ 1 (mod 4) og x ≡ 4 (mod 6) kan aldrig gælde samtidig: den første gør x ulige og den anden lige. Et helt system har en løsning netop når hvert par af dets ligninger har en, og sådan finder lommeregneren de to, der støder sammen.
Ofte stillede spørgsmål
Hvad siger den kinesiske restklassesætning?
Hvis ingen to af moduli n₁, n₂, … har en fælles faktor, så findes der for vilkårlige rester a₁, a₂, … præcis ét x fra 0 til N − 1 med x ≡ aᵢ (mod nᵢ) for hvert i, hvor N er produktet af moduli. Enhver anden løsning adskiller sig fra den med et multiplum af N: for Sunzis opgave er løsningerne 23, 128, 233 og så videre, én for hver 105.
Hvorfor kaldes den kinesisk?
Den ældste kendte opgave af denne slags står i Sunzi Suanjing, en kinesisk regnebog skrevet mellem 3. og 5. århundrede: talt tre, fem og syv ad gangen giver et antal ting resterne 2, 3 og 2. Qin Jiushao gav en generel metode til sådanne opgaver i 1247, og Carl Friedrich Gauss formulerede sætningen i dens moderne form i 1801.
Hvad hvis moduli ikke er indbyrdes primiske?
Så er der måske ingen løsning, og hvis der er en, gentages den for hvert mindste fælles multiplum af moduli i stedet for hvert produkt. To ligninger stemmer overens, når deres rester er ens modulo gcd af deres moduli. Ægopgaven bruger 2, 3, 4, 5, 6 og 7, der har fælles faktorer, og har alligevel en løsning: 301, der gentages for hver 420.
Hvordan bruger RSA den kinesiske restklassesætning?
At dekryptere en RSA-besked betyder at beregne c^d mod n, hvor n = p × q. Det er hurtigere at beregne c^d mod p og c^d mod q hver for sig, med eksponenten reduceret mod p − 1 og q − 1, og samle de to resultater med sætningen. Med tal, der er halvt så lange, koster hver af de to potenser omkring en ottendedel af arbejdet, så dekrypteringen er omkring fire gange hurtigere, og det meste RSA-software gør det sådan.
Hvor store må tallene være?
Op til 20 ligninger med tal på op til 200 cifre hver. Lommeregneren regner med eksakte heltal i din browser, så svaret er eksakt, uanset hvor langt det er, og intet sendes nogen steder hen.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor