primtallsfaktorisering

Primtallsfaktorisering er prosessen med å uttrykke et heltall som et produkt av primtall, der hvert primtall brukes med en viss eksponent. Grunnsetningen om primtallsfaktorisering sier at hvert heltall større enn 1 kan faktoriseres som et produkt av primtall på en unik måte opp til rekkefølgen. Faktoriseringen er grunnleggende i tallteorien og har implikasjoner i områder som brøkforenkling, divisibility og kryptografi.

Den mest grunnleggende metoden er prøvedeling (trial division). Man deler tallet med kjente primtall inntil man finner en faktor, og gjentar prosessen med kvotienten. Tiden er vanligvis O(sqrt(n)) i naive implementasjoner. For effektivisering brukes primtall opp til kvadratroten av tallet, ofte generert av Eulers primtalls-sieve (sieve of Eratosthenes), og deling gjøres kun med primtallene. Ytelsesmessige teknikker inkluderer wheel factorization og andre optimeringer som å dele ut faktor 2 først og deretter kun oddetall-primer.

For store tall benyttes mer avanserte algoritmer som Pollard's rho (også probabilistisk), elliptic curve factorization (ECM) og den generelle tallfelt-sieve (GNFS) for svært store tall. Mange av disse metodene har betydelig teoretisk og praktisk betydning fordi faktorering av store tall er vanskelig, og sikkerheten til kryptosystemer som RSA avhenger av dette.

Eksempel: 360 = 2^3 × 3^2 × 5.

Anvendelser inkluderer kryssjekk i kryptografi, forenkling av brøker, løsning av visse diophantiske problemer og forskning i tallteori.