primfaktorene

Primfaktorer er primtall som multiplisert gir et heltall. En primfaktorisering av et tall n > 1 er skrivemåten som produkt av primtall, ofte vist som n = p1^a1 * p2^a2 * ... * pk^ak, der pi er primtall og ai er positive heltall. For eksempel er 84 = 2^2 * 3 * 7.

Et primtall er et heltall større enn 1 som bare har to positive divisorer: 1 og seg selv. Hvis et tall kan skrives som et produkt av primtall, kalles de faktorene primfaktorer. Enhver faktorisering brytes ned til primtallene i en unik måte, og man snakker om primfaktorisering av n.

Hovedsetningen om aritmetikk sier at hvert heltall større enn 1 kan faktoriseres som et produkt av primtall, og denne faktoriseringen er unik opp til rekkefølgen av faktorene. Dette kalles også den unike faktoriseringen.

Vanlige metoder for å finne primfaktorer inkluderer enkel deling med primtall opp til kvadratroten av tallet (trial division). For større tall brukes mer avanserte algoritmer og forhånds genererte primetabeller. Faktorisering spiller en viktig rolle i praktiske oppgaver som å forenkle brøker, beregne største felles divisor og finne modulararitmetiske egenskaper.

Anvendelser inkluderer også kryptografi: RSA-kryptering baserer seg på vanskeligheten ved å faktorisere store tall som er produkt av to store primtall, noe som gjør sikker nøkkelutveksling avhengig av primfaktoreringens kompleksitet.