Primtal

Att ta reda på om ett tal är ett primtal eller ej är lite klurigare än man kan tro. Egentligen handlar det bara om att försäkra sig om att talet inte är jämnt delbart med något lägre tal vilket i teorin inte är svårt alls. Men om man hanterar väldigt stora tal som till exempel nycklar vid kryptering och liknande så blir det i praktiken ganska tidsödande att testa alla lägre tal.

Eratosthenes såll är en naiv algoritm som utvecklades av den gamla greken Eratosthenes runt år -200. Algoritmen tar en övre gräns och sållar bort allt som inte är primtal under gränsen. Efteråt finns bara primtalen kvar. Själva sållningen går till så att man börjar från 2 och plockar bort alla tal under gränsen som är delbara med 2. Sen tar man 3, plockar bort alla tal delbara med 3, fortsätt med 4 ... osv upp till gränsen. På kodsidan finns algoritmen implementerad i flera olika programmeringsspråk.

Om man nu bara är intresserad av att testa om ett enda tal (x) är ett primtal så kan man använda en förenklad version av Eratosthenes såll. Det räcker då att kolla att x inte är jämnt delbart med något tal under x med en loop som den nedan.

  bool testForPrime(int x)
  {
     for (int i = 2; i < x; i++) {
        if (x % i == 0) {
           // Inte primtal.
           return false;
        }
     }
     // Primtal!!
     return true;
  }
  

Det är ganska lätt att förbättra prestandan i Eratosthenes såll genom att utnyttja det vi vet om primtal och delbarhet. Till exempel vet vi att inga jämna tal förutom två kan vara primtal, så givet att x!=2 måste LSB vara ett för att det ens ska vara värt att testa något. Givet det vet vi också att x inte kan vara jämnt delbart med något tal större än x/3. Vi får då ett lite effektivare test.

  bool testForPrime(int x)
  {
     int upperLimit;

     // Inga jämna tal förutom två kan vara primtal
     if (x == 2)
        return true;
     else if (x & 1 == 0)
        return false;

     // Testa endast udda tal upp till x/3
     upperLimit = x / 3;
     for (int i = 3; i <= upperLimit; i += 2) {
        if (x % i == 0) {
           // Inte primtal.
           return false;
        }
     }
     // Primtal!!
     return true;
  }
  

Stora primtal

Om det nu är kryptologi man är ute efter och vill testa riktigt stora tal (tal med 30-40 siffror) så är dessa metoder inte praktiska eftersom de tar för lång tid. En populär metod som ofta används för generering av nycklar vid till exempel RSA-kryptering är witness.

Witness är en algoritm som kontrollerar om ett tal inte kan vara ett primtal. Om algoritmen svarar sant är talet garanterat inte ett primtal, om resultatet är falskt kan det vara ett primtal. Sannorlikheten för att witness ska svara fel är mindre än 0,5. Detta innebär att om algoritmen anropas ett antal gånger i rad och den svarar falskt varje gång så kan man till slut vara ganska säker på att det är ett primtal. Det är naturligtvis en slump inblandad här, annars skulle ju svaret alltid vara det samma.

Algoritmen finns implementerad på kodsidan. Den anropas med två tal, slump och prima. prima är talet vi vill testa om det kan vara ett primtal och slump är ett slumptal som är lägre än prima. Eftersom slump ska vara lägre än prima och det inte fungerar så bra med 0 och 1 så funkar denna implementation av algoritmen inte jättebra på de lägsta talen (1 kommer till exempel att klassas som "inte primtal"). Men eftersom vi är ute efter riktigt stora tal här så kanske det inte gör så mycket.

Tillbaka till indexet