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ő 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,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. é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 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 (): #include <stdio.h>

int main(void) { int t; 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 -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 Prímtényező Kanonikus alak Kanonikus alakok listája RSA-eljárás

Jegyzetek

Irodalom Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313. Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. . Section 4.5.4: Factoring into Primes, pp. 379–417. .

További információk Alice és Bob - 16. rész: Alice és Bob alaptétele msieve – SIQS and NFS – has helped complete some of the largest public factorizations known Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp. 3–22. download Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781–793 (2004). August 2005 version PDF Eric W. Weisstein, “RSA-640 Factored” MathWorld Headline News, November 8, 2005 Dario Alpern's Integer factorization calculator – A web app for factoring large integers

Kategória:Számelmélet Kategória:Számítógép-tudomány