Primtalsfaktorisering

Från Rilpedia

Texten från svenska Wikipedia

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

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

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 . De tal som ger resten noll är faktorer av n. Trial division är den överlägset mest effektiva 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 divison 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 Erathostenes såll, kvadratiska såll och talkroppssåll. Mest effektiv är general number field sieve (GNFS), som använts 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

Källor

Den här artikeln saknar källhänvisningar. Förbättra gärna artikeln genom att lägga till pålitliga källor (helst fotnoter). Material som inte kan verifieras kan ifrågasättas eller tas bort. (juni 2009)

Litteratur

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