Prímfelbontás

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.

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ő ${\displaystyle p_{1}\,}$  prímmel.
  • Ha az osztás maradék nélküli, kezdjük újra az algoritmust az ${\displaystyle {\frac {n}{p_{1}}}}$  értékkel, s adjuk hozzá ${\displaystyle 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ő ${\displaystyle p_{2}\,}$  prímmel, és így tovább, amíg az aktuális ${\displaystyle {\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 ${\displaystyle p_{i}\,}$  prímmekkel osztani n-t melyekre igaz, hogy ${\displaystyle 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 (${\displaystyle 2^{64}-1}$ ):

#include    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; } 

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 ${\displaystyle {\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.

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

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