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.
 |
Ez a matematikai tárgyú lap még csak csonk (azaz erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
Based on work by 