Primtalsfaktorisering

Från Wikipedia
Hoppa till: navigering, sök

Primtalsfaktorisering eller heltalsfaktorisering 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 bortsett från faktorernas inbördes ordning.

Algoritmer[redigera | redigera wikitext]

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 mest effektiva metoden för att bestämma små faktorer, exempelvis mindre än 109, 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. Mest effektiv är general number field sieve (GNFS), som använts för att faktorisera RSA-tal med 100-siffriga faktorer.

Tillämpbarhet[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Tryckta källor[redigera | redigera wikitext]

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