Prímfelbontás

A Wikipédiából, a szabad enciklopédiából
(Kanonikus felbontás szócikkből átirányítva)

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[szerkesztés]

Leírás[szerkeszté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ő prímmel.
    • Ha az osztás maradék nélküli, kezdjük újra az algoritmust az értékkel, s adjuk hozzá -et az n prímtényezős listájához.
    • Ha az osztás maradékos volt, akkor osszuk n-t a következő prímmel,[1] és így tovább, amíg az aktuális érték 1 nem lesz, maradék nélkül. Ekkor megállunk.

Megjegyezzük, hogy elég csupán azokkal a prímmekkel osztani n-t melyekre igaz, hogy .

Példa[szerkesztés]

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[szerkesztés]

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 ():

#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[szerkesztés]

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 -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[szerkesztés]

Jegyzetek[szerkesztés]

  1. Elég itt egyesével léptetni a számot, ugyanis ha p1+1 nem prím akkor azzal nem lesz osztható a szám, tehát automatikusan léptetjük. Ez azért van, mert összetett számnak van magánál kisebb prímosztoja, ami az algoritmus szerint már szerepelt a ciklusban.

További információk[szerkesztés]