Kalkulačka teórie čísel — prvočísla, NSD/NSN, modulárna aritmetika & ďalšie
Kalkulačka teórie čísel
Preskúmať prvočísla, rozklad na súčin, najväčšieho spoločného deliteľa, modulárnu aritmetiku a ďalšie.
Všetky výpočty sa vykonávajú lokálne v prehliadači — vstup sa nikdy neodosiela.
Režim:
Kontrola prvočísel
Zadá sa číslo a klikne sa na „Skontrolovať“
Tip: Používa deterministický test Miller-Rabin pre čísla až do 264.
Kliknutím na „Ďalšie prvočíslo“ alebo „Predchádzajúce prvočíslo“ sa nájdu blízke prvočísla.
Rozklad na prvočísla
Zadá sa číslo a klikne sa na „Rozložiť“
Tip: Podporuje celé čísla až do 1015. Rozklad stromom súčiniteľov so zápisom prvočísel a mocnín.
Kalkulačka NSD a NSN
Zadajú sa čísla a klikne sa na NSD, NSN alebo Obe
Tip: Zadajú sa 2 alebo viac celých čísel oddelených čiarkami. NSD sa počíta Euklidovým algoritmom; NSN sa počíta ako |a*b|/(a,b).
Modulárna aritmetika
Zadajú sa a, b, m a klikne sa na operáciu
Tip: Modulárne umocňovanie používa rýchle umocňovanie (štvorenie a násobenie).
Modulárna inverzia existuje len vtedy, keď sú a a m nesúdeliteľné.
Delitele a funkcie deliteľov
Zadá sa číslo a klikne sa na „Vypočítať“
Tip: Vypíše všetky kladné delitele, počet deliteľov d(n), súčet deliteľov σ(n)
a vlastné delitele. Podporuje čísla až do 1012.
Totient a aritmetické funkcie
Zadá sa číslo a klikne sa na „Vypočítať“
Tip: Počíta Eulerov totient φ(n), Möbiovu funkciu μ(n),
σ(n), d(n) a príbuzné aritmetické funkcie.
Prvočísla a kongruencie
Prvočíslo má presne dva deliteľy, 1 a samo seba; každé celé číslo väčšie než 1 sa rozkladá na prvočísla práve jedným spôsobom (základná veta aritmetiky). Kongruencia a ≡ b (mod n) znamená, že n delí a−b — aritmetika na ciferníku hodín, kde 10 + 5 ≡ 3 (mod 12), a základ NSD, NSN a modulárneho umocňovania.
Vynásobiť dve veľké prvočísla je okamžité, ale získať ich späť zo súčinu je výpočtovo brutálne — táto jednosmerná asymetria je základom šifrovania RSA a dôvod, prečo φ(n) modulu s 2048 bitmi nie je verejné.
