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 1-nél nagyobb 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 volna igénybe egy 200 jegyű szám felbontása becslési eljárásokkal történt számítások szerint. 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}\leq {\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, a 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, a 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 és 18 446 744 073 709 551 615 közötti számok faktorizációjára ($2^{64}-1$):

#include <stdio.h>
 
int main(void) {
	int t[100];
    unsigned long long j, i, k, d; //ha csak a pozitív számokat vesszük
    while (1==scanf("%llu", &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.

Mivel az osztók párban helyezkednek el, ezért elég ${\sqrt {n}}$-ig ellenőrizni a számokat, hogy van-e osztó.

É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.

Kapcsolódó szócikkek

• Prímtényező
• Kanonikus alak
• Kanonikus alakok listája
• RSA-eljárás

További információk

• Alice és Bob - 16. rész: Alice és Bob alaptétele