Calculator de teoria numerelor — numere prime, CMMDC/CMMMC, aritmetică modulară și altele
Calculator de teoria numerelor
Explorează numere prime, factorizarea, cel mai mare divizor comun, aritmetica modulară și altele.
Toate calculele se efectuează local în browser — intrarea nu se încarcă niciodată.
Mod:
Verificator de numere prime
Se introduce un număr și se apasă „Verifică”
Sfat: se folosește testul Miller-Rabin determinist pentru numere până la 264.
Se apasă „Următorul prim” sau „Precedentul prim” pentru a găsi numere prime apropiate.
Factorizare în numere prime
Se introduce un număr și se apasă „Factorizează”
Sfat: acceptă numere întregi până la 1015. Descompunere în arbore de factori cu reprezentare prin exponenți de numere prime.
Calculator CMMDC și CMMMC
Se introduc numere și se apasă CMMDC, CMMMC sau Ambele
Sfat: se introduc 2 sau mai multe numere întregi separate prin virgulă. CMMDC folosește algoritmul lui Euclid; CMMMC se calculează ca |a*b|/(a,b).
Aritmetică modulară
Se introduc a, b, m și se apasă o operație
Sfat: exponențierea modulară folosește exponențierea rapidă (pătrat-și-înmulțire).
Inversul modular există doar când a și m sunt prime între ele.
Divizori și funcții de divizori
Se introduce un număr și se apasă „Calculează”
Sfat: listează toți divizorii pozitivi, numărul de divizori d(n), suma divizorilor σ(n),
și divizorii proprii. Acceptă numere până la 1012.
Funcția lui Euler și funcții aritmetice
Se introduce un număr și se apasă „Calculează”
Sfat: calculează funcția lui Euler φ(n), funcția lui Möbius μ(n),
σ(n), d(n) și funcțiile aritmetice conexe.
Numere prime și congruențe
Un număr prim are exact doi divizori, 1 și el însuși; fiecare număr întreg mai mare decât 1 se descompune în numere prime într-un singur mod (teorema fundamentală a aritmeticii). Congruența a ≡ b (mod n) înseamnă că n divide a−b — aritmetica de pe cadranul unui ceas, unde 10 + 5 ≡ 3 (mod 12), și baza CMMDC, CMMMC și a exponențierii modulare.
Înmulțirea a două numere prime mari este instantanee, dar recuperarea lor din produs este extrem de costisitoare din punct de vedere computațional — această asimetrie unidirecțională stă la baza criptării RSA și de aceea φ(n) pentru un modul de 2048 de biți nu este public.
