Prímfelbontás

A számelméletben a prímfelbontás (törzstényezős felbontás, esetleg prímfaktorizáció) az a folyamat, amikor egy összetett számot prím osztóira (törzstényezőire) bontjuk (faktorizáljuk). A törzstényezők szorzata az eredeti egész számmal egyenlő. Az eljárás eredménye prímek (prímhatványok) szorzata. Ezt a formulát az eredeti szám kanonikus alakjának nevezzük.

A számelmélet alaptétele szerint minden pozitív egész szám egyértelműen, azaz egy és csak egyféleképpen bontható fel prímszámok szorzatára.

Nagy számok esetében nem ismerünk minden esetben hatékony algoritmust a prímtényezőkre bontásra; nemrégiben egy az RSA-eljárás által kiírt pályázaton mintegy másfél évet, és kb. fél évszázadnyi gépidőt vett igénybe egy 200 jegyű szám felbontása ^[forrás?]. A prímtényezőkre bontás feltételezett bonyolultságát számos kriptográfiai algoritmus használja ki. A matematika és az informatika számos területe foglalkozik a problémával, köztük az elliptikus görbék, algebrai számelmélet és a kvantumszámítógépek területei.

Adott hosszúságú számok közül vannak könnyebben és nehezebben faktorizálhatók. Jelenlegi tudásunk szerint a legnehezebb esetek közé tartoznak a két, véletlenül választott, közel azonos nagyságú prímszám szorzataként előálló számok.

Ez a szócikk egy példát mutat olyan algoritmusra, ami jól működik olyan számokon, ahol a prímtényezők kicsik.

Egy egyszerű faktorizáló eljárás

Leírás

Az alábbiakban leírunk egy rekurzív eljárást számok prímtényezős felbontására: Adott egy n szám

• ha n prím, készen vagyunk, megvan a prímtényezős felbontás.
• ha n összetett, osszuk el n-t az első $p_1\,$ prímmel.
  • Ha az osztás maradék nélküli, kezdjük újra az algoritmust az $\frac{n}{p_1}$ értékkel, s adjuk hozzá $p_1\,$-et az n prímtényezős listájához.
  • Ha az osztás maradékos volt, akkor osszuk n-t a következő $p_2\,$ prímmel, és így tovább, amíg az aktuális $\frac{n}{p_i}$ érték 1 nem lesz, maradék nélkül. Ekkor megállunk.

Megjegyezzük, hogy elég csupán azokkal a $p_i\,$ prímmekkel osztani n-t melyekre igaz, hogy $p_i \le \sqrt{n}$.

Példa

Adott 9438, ennek szeretnénk megkapni a prímtényezős felbontását.

9438/2 = 4719 , a maradék 0, tehát 2 prímtényezője 9438-nak. megismételjük az eljárást 4719-cel

4719/2 = 2359, a maradék 1, tehát 2 NEM prímtényezője 4719-nek. a következő prímmel, a 3-mal próbálkozunk

4719/3 = 1573, a maradék 0, tehát 3 prímtényezője 4719-nek (azaz 9438-nak is). megismételjük az algoritmust 1573-mal

1573/3 = 524, a maradék 1, tehát a 3 NEM prímtényezője 1573-nak. a következő prímmel, az 5-tel próbálkozunk

1573/5 = 314, a maradék 3, tehát az 5 NEM prímtényezője 1573-nak. a következő prímmel, az 7-tel próbálkozunk

1573/7 = 224, a maradék 5, tehát 7 NEM prímténezője 1573-nak. a következő prímmel, az 11-gyel próbálkozunk

1573/11 = 143, a maradék 0, tehát 11 prímtényezője 1573-nak (azaz 9438-nak is). megismételjük az eljárást 143-mal

143/11 = 13, a maradék 0, tehát 11 prímtényezője 143-nak (azaz 9438-nak is). megismételjük az algoritmust 13-mal

13/11 = 1, de a maradék 2, tehát 11 NEM prímtényezője 13-nak. a következő prímmel, a 13-mal próbálkozunk

13/13 = 1, a maradék 0, tehát 13 prímtényezője 13-nak (azaz 9438-nak is). Megállunk, mert elértünk 1-hez

így a végére a következőt kapjuk 9438 = 2 × 3 × 11 × 11 × 13.

Programkód

Alábbiakban pedig láthatunk egy C programnyelven írt algoritmust 2 147 483 647-nél kisebb számok faktorizációjára ($2^{31}-1$):

  #include <stdio.h>
 int t[34];
 int main(void) {
  int j, i, k, c=0, d;
  while (1==scanf("%d", &k)) {
   if (k<0) k*=(-1);
   i=0;
   d=2;
   while (k>1) {
     if (k%d==0) {
         k/=d; 
         t[i]=d;
         i++;
     } 
     else {
         ++ d;
     }
   }
   for (j=0;j<i;j++) {
    printf("%d ", t[j]);
   }
   printf("\n\n");
  }
  return 0;
 }

Időhiány

A fent vázolt algoritmus jól működik kis n-re, de kivitelezhetetlenné válik ahogy az n egyre nagyobb szám lesz. Például egy 18 jegyű (másképp 60 bites) szám esetén, minden 1 000 000 000-nál kisebb prímet tesztelni kell, ami még egy számítógépnek is nehéz feladat. Két jeggyel növelve a számot, a faktorizáció számításigénye a 10-szeresére növekszik.

Épp ez, a nagy (több száz jegyű) számok faktorizációjának (időbeli) problémája adja az alapját a modern kriptográfiának. És ez ösztönzi a kutatást olyan gyors eljárás után, mely polinom időn belül képes faktorizálni. A dolog jellegéből fakadóan, ha meg is születik (született?) egy hatékony algoritmus, az – Babbage eredményeihez hasonlóan – sokáig katonai titoknak fog számítani, mert hatalmas stratégiai jelentősége van.

Lásd még

• Kanonikus alakok listája
• RSA-eljárás