„Prímfelbontás” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Visszaállítottam a lap korábbi változatát: 80.99.23.200 (vita) szerkesztéséről Legobot szerkesztésére |
a hiv. korr, AWB |
||
1. sor:
A [[számelmélet]]ben a '''prímfelbontás''' (''törzstényezős felbontás'', esetleg ''prímfaktorizáció'') az a folyamat, amikor egy [[összetett számok|összetett számot]] [[Prímszámok|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 alak]]jának nevezzük.
[[A számelmélet alaptétele]] szerint minden pozitív egész szám egyértelműen, azaz egy és csak egyféleképpen bontható fel [[
Nagy számok esetében nem ismerünk minden esetben hatékony [[algoritmus]]t a prímtényezőkre bontásra; nemrégiben egy az [[RSA|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áfia]]i algoritmus használja ki. A [[matematika]] és az [[informatika]] számos területe foglalkozik a problémával, köztük az [[Elliptikus görbe|elliptikus görbék]], [[algebrai számelmélet]] és a [[kvantumszámítógép]]ek területei.
17. sor:
* ha ''n'' összetett, osszuk el ''n''-t az első <math>p_1\,</math> prímmel.
**Ha az osztás maradék nélküli, kezdjük újra az algoritmust az <math>\frac{n}{p_1}</math> értékkel, s adjuk hozzá <math>p_1\,</math>-et az ''n'' prímtényezős ''listájához''.
**Ha az osztás maradékos volt, akkor osszuk ''n''-t a következő <math>p_2\,</math> prímmel, és így tovább, amíg az aktuális <math>\frac{n}{p_i}</math> érték 1 nem lesz, maradék nélkül. Ekkor megállunk.
Megjegyezzük, hogy elég csupán azokkal a <math>p_i\,</math> prímmekkel osztani ''n''-t melyekre igaz, hogy <math>p_i \le \sqrt{n}</math>.
| |||