Primtalsfaktorisering

Primtalsfaktorisering innebär att ett heltal skrivs som en produkt av primtal. Exempelvis har talet 456 faktoriseringen

$456=2^{3}\cdot 3\cdot 19.$

Enligt aritmetikens fundamentalsats har varje positivt heltal en primtalsfaktorisering som är unik om man bortser från faktorernas inbördes ordning.

Heltalsfaktorisering kallas den allmännare process i vilken ett heltal skrivs som en produkt av mindre men inte nödvändigtvis prima heltal. Till skillnad från primtalsfaktorisering är resultatet av en heltalsfaktorisering inte alltid unikt. Till exempel är både $2\cdot 6$ och $3\cdot 4$ giltiga heltalsfaktoriseringar av talet 12.

Algoritmer

Ett flertal algoritmer används för primtalsfaktorisering. Den enklaste är trial division, vilken innebär att man för ett tal n testar att dividera n med varje tal upp till och med ${\sqrt {n}}$. De tal som ger resten noll är faktorer av n. Trial division är den överlägset effektivaste metoden för att bestämma små faktorer, exempelvis mindre än 10⁹, men oanvändbart för att hitta väsentligt större faktorer. Lyckligtvis är metoden effektiv för slumpmässigt valda tal, eftersom hälften av alla tal har 2 som faktor, en tredjedel har 3 som faktor, och så vidare. Hela 88% av alla heltal har minst en faktor som är mindre än 100. Trial division kan därför användas för att snabbt röja undan små faktorer varefter en mer avancerad algoritm tar hand om de återstående.

De enklaste metoderna för att snabbt hitta faktorer något större än cirka 10 siffror är Pollards rho-metod och Pollards p-1-metod samt varianter av dessa. För faktorer i storleksordningen 20 – 25 siffror är ECM (faktorisering med elliptiska kurvor) ytterligare ett alternativ. De enda praktiska algoritmerna för större faktorer än så är varianter av Eratosthenes såll, kvadratiska såll och talkroppssåll. Effektivast är general number field sieve (GNFS), som används för att faktorisera RSA-tal med 100-siffriga faktorer.

Tillämpbarhet

Det tycks som om det beräkningsmässigt är betydligt svårare att bestämma primtalsfaktorerna till ett givet tal än att multiplicera ihop faktorer. Det är också enklare att med ett primtalstest avgöra huruvida ett tal kan delas upp i mindre faktorer än att om så är fallet bestämma faktorerna. Datorer kan idag enkelt multiplicera tal med miljontals siffror och utföra primtalstest på tal med tusentals siffror, men att faktorisera ett 100-siffrigt tal är ett utmanande problem. Svårigheten att faktorisera heltal utnyttjas av krypteringsalgoritmer som RSA.

Referenser

Tryckta källor

• Kodboken, Simon Sing. Kryptografins historia där RSA-kryptering nämns.