Calculator pentru teorema chineză a resturilor
Numărați o grămadă de lucruri câte trei și rămân 2, câte cinci rămân 3, câte șapte rămân 2: sunt 23, sau 128, sau 233, câte un răspuns la fiecare 105. Aceasta este problema din Sunzi Suanjing care a dat numele teoremei chineze a resturilor. Scrieți orice sistem de congruențe x ≡ a (mod n), cu oricâte ecuații și numere oricât de mari, și vedeți răspunsul, calculul cu numerele dumneavoastră și o imagine care arată de ce funcționează. Când ecuațiile nu pot fi toate adevărate, calculatorul numește cele două care se contrazic și arată de ce. Scrieți ecuațiile x ≡ a (mod n), câte una pe rând: a este restul, iar n modulul. Adăugați un rând cu Adaugă ecuație sau cu Enter în ultimul modul și ștergeți unul cu ×. Merg numere întregi de până la 200 de cifre, iar a poate fi negativ. Sau alegeți un exemplu rezolvat. Casetele arată cea mai mică soluție și din cât în cât se repetă; sub ele sunt primele soluții pozitive și o verificare a fiecărei ecuații. Imaginea marchează numerele care satisfac fiecare ecuație, iar coloana în care fiecare rând are un marcaj este soluția; tabelul resturilor arată două ecuații deodată. Calculul este scris cu numerele dumneavoastră, prin construcția din manual sau prin substituție.
Cum funcționează
- Scrieți ecuațiile x ≡ a (mod n), câte una pe rând, sau alegeți un exemplu rezolvat, cum ar fi problema lui Sunzi, coșul cu ouă sau perioada iuliană.
- Citiți cea mai mică soluție, modulul cu care se repetă și primele soluții pozitive, fiecare verificată în fiecare ecuație.
- Urmăriți calculul pas cu pas, prin construcție sau prin substituție, și comutați imaginea între axa numerelor și tabelul resturilor.
Cum funcționează construcția
Când niciun doi moduli nu au un factor comun, soluția se poate construi direct. Înmulțiți modulii: pentru problema lui Sunzi, N = 3 × 5 × 7 = 105. Pentru fiecare ecuație luați Nᵢ = N / nᵢ, un multiplu al fiecărui alt modul: 35, 21 și 15. Apoi găsiți inversul yᵢ al lui Nᵢ mod nᵢ cu algoritmul lui Euclid extins: 35 dă restul 2 la împărțirea la 3, iar 2 × 2 = 4 ≡ 1 (mod 3), deci y₁ = 2; 21 și 15 dau restul 1, deci inversele lor sunt 1. Acum x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, iar 233 mod 105 = 23. Fiecare termen se potrivește propriei ecuații și este multiplu al celorlalți moduli, deci suma se potrivește tuturor.
Când modulii au un factor comun
Și un sistem ai cărui moduli au factori comuni poate avea soluție. Două ecuații x ≡ a (mod m) și x ≡ b (mod n) pot fi adevărate în același timp exact când a − b este multiplu de gcd(m, n), iar soluția se repetă atunci la fiecare lcm(m, n) în loc de fiecare m × n. Două autobuze care pleacă la minutele 5 și 11, la fiecare 12 și la fiecare 18 minute, se întâlnesc la minutul 29 și apoi la fiecare 36 de minute, pentru că 11 − 5 = 6 este multiplu de gcd(12, 18) = 6. Dar x ≡ 1 (mod 4) și x ≡ 4 (mod 6) nu pot fi niciodată adevărate împreună: prima face x impar, iar a doua par. Un sistem întreg are soluție exact când fiecare pereche de ecuații ale sale are, și așa găsește calculatorul cele două care se contrazic.
Întrebări frecvente
Ce spune teorema chineză a resturilor?
Dacă niciun doi dintre modulii n₁, n₂, … nu au un factor comun, atunci pentru orice resturi a₁, a₂, … există exact un x de la 0 la N − 1 cu x ≡ aᵢ (mod nᵢ) pentru fiecare i, unde N este produsul modulilor. Orice altă soluție diferă de el printr-un multiplu de N: pentru problema lui Sunzi, soluțiile sunt 23, 128, 233 și așa mai departe, câte una la fiecare 105.
De ce se numește chineză?
Cea mai veche problemă cunoscută de acest fel se află în Sunzi Suanjing, o carte de aritmetică chinezească scrisă între secolele III și V: numărate câte trei, câte cinci și câte șapte, niște lucruri dau resturile 2, 3 și 2. Qin Jiushao a dat o metodă generală pentru astfel de probleme în 1247, iar Carl Friedrich Gauss a enunțat teorema în forma ei modernă în 1801.
Ce se întâmplă dacă modulii nu sunt primi între ei?
Atunci s-ar putea să nu existe soluție, iar când există, se repetă la fiecare cel mai mic multiplu comun al modulilor în loc de fiecare produs. Două ecuații se potrivesc când resturile lor sunt egale modulo gcd-ul modulilor lor. Ghicitoarea cu ouăle folosește 2, 3, 4, 5, 6 și 7, care au factori comuni, și totuși are soluție: 301, care se repetă la fiecare 420.
Cum folosește RSA teorema chineză a resturilor?
A decripta un mesaj RSA înseamnă a calcula c^d mod n, unde n = p × q. Este mai rapid să calculezi separat c^d mod p și c^d mod q, cu exponentul redus mod p − 1 și q − 1, și să unești cele două rezultate cu teorema. Cu numere de două ori mai scurte, fiecare dintre cele două puteri cere circa o optime din muncă, deci decriptarea este de circa patru ori mai rapidă, iar majoritatea programelor RSA procedează așa.
Cât de mari pot fi numerele?
Până la 20 de ecuații, cu numere de cel mult 200 de cifre fiecare. Calculatorul lucrează cu numere întregi exacte în browserul dumneavoastră, deci răspunsul este exact oricât de lung ar fi, iar nimic nu este trimis nicăieri.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor