| dbo:abstract
|
- 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 igénybe egy 200 jegyű szám felbontása [forrás?]. 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. (hu)
- 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 igénybe egy 200 jegyű szám felbontása [forrás?]. 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. (hu)
|
