Talteoriberegner — primtal, STF/MFM, modulær aritmetik & mere
Talteoriberegner
Udforsk primtal, faktorisering, største fælles divisorer, modulær aritmetik og meget mere. Alle beregninger udføres lokalt i browseren — input uploades aldrig.
Tilstand:
Primtalstjek
Indtast et tal, og klik på "Tjek"
Tip: Bruger deterministisk Miller-Rabin for tal op til 264. Klik på "Næste primtal" eller "Forrige primtal" for at finde nærliggende primtal.
Primtalsfaktorisering
Indtast et tal, og klik på "Faktorisér"
Tip: Understøtter hele tal op til 1015. Faktortrædekomposition med primtalspotens-repræsentation.
STF- & MFM-beregner
Indtast tal, og klik på STF, MFM eller Begge
Tip: Indtast 2 eller flere hele tal adskilt af komma. STF bruger den euklidiske algoritme; MFM beregnes som |a*b|/(a,b).
Modulær aritmetik
Indtast a, b, m, og klik på en operation
Tip: Modulær potensering bruger hurtig potensering (kvadrér og multiplicér). En modulær invers findes kun, når a og m er indbyrdes primiske.
Divisorer & divisorfunktioner
Indtast et tal, og klik på "Beregn"
Tip: Viser alle positive divisorer, antallet af divisorer d(n), summen af divisorer σ(n) og ægte divisorer. Understøtter tal op til 1012.
Et primtal har præcis to divisorer, 1 og sig selv; hvert helt tal større end 1 faktoriseres i primtal på præcis én måde (aritmetikkens fundamentalsætning). Kongruens a ≡ b (mod n) betyder, at n går op i a−b — regning på en urskive, hvor 10 + 5 ≡ 3 (mod 12), og grundlaget for STF, MFM og modulær potensering.
At gange to store primtal sammen er øjeblikkeligt, men at genskabe dem ud fra produktet er beregningsmæssigt brutalt — denne ensrettede asymmetri er det, RSA-kryptering bygger på, og derfor er φ(n) for et 2048-bit modul ikke offentligt.
