Primtallfaktorisering-kalkulator
Skriv inn et positivt heltall og se hvilke primtall det er bygget opp av.
Hvordan bruke kalkulatoren
- Skriv inn et positivt heltall (2 eller høyere).
- Kalkulatoren viser hvilke primtall tallet består av, og hvor mange ganger hvert primtall inngår.
Hva er primtallfaktorisering?
Aritmetikkens fundamentalteorem sier at ethvert heltall større enn 1 kan skrives som et unikt produkt av primtall (tall som kun er delelig med 1 og seg selv). For eksempel er 360 = 2³ × 3² × 5. Primtallfaktorisering brukes blant annet til å finne minste felles multiplum og største felles faktor, forenkle brøker, og er sentralt i kryptografi.
I kryptografi er primtallfaktorisering selve grunnlaget for RSA-kryptering, et av de mest brukte krypteringssystemene på nett: det er lett å multiplisere to store primtall sammen, men svært tungt å regne baklengs og finne primfaktorene til et stort tall — denne asymmetrien er det som gjør RSA sikkert i praksis.
For skoleelever er dette samme metoden som brukes til å forenkle brøker og finne minste felles multiplum (MFM) og største felles faktor (SFF) mellom to tall for hånd.
Lett å gange, vanskelig å faktorisere
Å gange to store primtall sammen er trivielt for en datamaskin. Å gå den andre veien — finne faktorene tilbake fra produktet — er dramatisk vanskeligere når tallene blir store nok. Denne asymmetrien er ikke en kuriositet: den er selve fundamentet for RSA, en av krypteringsmetodene som sikrer nettbank og HTTPS.
For små tall merker man ingenting av dette, og kalkulatoren her svarer momentant. Men vanskelighetsgraden vokser svært raskt med antall siffer, og for tall på flere hundre siffer finnes det ingen kjent metode som klarer det på realistisk tid med dagens datamaskiner. Aritmetikkens fundamentalteorem garanterer samtidig at faktoriseringen er entydig: hvert heltall over 1 har nøyaktig én primtallsfaktorisering.
Regneeksempel: 360 faktoriseres til 2³ × 3² × 5, altså 2 × 2 × 2 × 3 × 3 × 5 = 360. Faktoriseringen forteller mer enn den ser ut til: antall divisorer finner du ved å legge 1 til hver eksponent og gange dem sammen, (3+1) × (2+1) × (1+1) = 24. 360 har altså 24 delere, og det er nettopp derfor tallet ble valgt til å dele sirkelen i grader.
Ofte stilte spørsmål
Hva skjer hvis jeg skriver inn et primtall?
Da vises tallet selv med eksponent 1 — det er per definisjon sin egen eneste primfaktor.
Fungerer det for veldig store tall?
Ja, men beregningstiden øker for tall med store primfaktorer (spesielt hvis tallet selv er et stort primtall) — for de aller fleste praktiske tall er beregningen umiddelbar.
Hvorfor regnes ikke 1 som et primtall?
Per definisjon må et primtall ha nøyaktig to positive delere (1 og seg selv). Tallet 1 har kun én deler, og regnes derfor verken som primtall eller sammensatt tall.
Hva har primtallfaktorisering med kryptografi å gjøre?
RSA-kryptering, mye brukt på nett, baserer seg på at det er lett å multiplisere to store primtall, men svært tungt å regne baklengs og finne primfaktorene til et stort tall. Denne asymmetrien er selve sikkerhetsgrunnlaget.