Prímfelbontás

A Wikipédiából, a szabad lexikonból.

A számelméletben a prímfelbontás az a folyamat, amikor egy összetett számot prím osztóira bontjuk (faktorizáljuk), amik összeszorozva az eredeti egész számot adják.

A számelmélet alaptétele szerint minden pozitív egész szám egyértelműen felbontható 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 á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. 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, kb. azonos nagyságú prímszám szorzataként előálló számok.