Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
4. lecke: Modern kriptográfia- A számelmélet alaptétele
- Nyilvános kulcsú titkosítás – mi az?
- A diszkrét logaritmus probléma
- Diffie-Hellman kulcs-csere
- RSA-titkosítás: 1. lépés
- RSA-titkosítás: 2. lépés
- RSA-titkosítás: 3. lépés
- Komplexitás időfüggvénye (szemléltetés)
- Euler-féle Φ függvény
- Euler-féle Φ függvényértékek szemléltetése
- RSA-titkosítás: 4. lépés
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
A számelmélet alaptétele
Független megvalósítás egy előd szemszögéből. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Képzeld magad az őskorba! Most gondold el: hogyan követnéd az időt,
ha nincs órád? Minden óra valamilyen
ismétlődő mintázaton alapul, ami az idő múlását
egyforma időközökre bontja. Az ismétlődő mintázatot
az égbolton keressük. A nap minden nap felkel és lemegy.
Ez a legkézenfekvőbb. De hosszabb időszakhoz hosszabb ciklust kerestünk. Úgyhogy a holdat figyeltük meg, ami több napon keresztül
fokozatosan megnő, majd elfogy. Amikor megszámoljuk
a napokat két telihold között, 29-et kapunk. Innen ered a hónap. De ha a 29-et egyenlő részekre
szeretnénk osztani, akadályba ütközünk. Nem lehet megcsinálni. 29-et csak úgy tudunk
egyenlő részekre osztani, ha minden részben
egy egység van. A 29 primszám. Feloszthatatlanként gondolhatunk rá. Ha egy szám egynél nagyobb
egyforma számok összegére bontható, összetett számnak nevezzük. Kíváncsiak lehetünk rá,
hogy hány prímszám létezik, és mekkora értéket vehetnek fel. Kezdjük azzal, hogy
két csoportba osztjuk a számokat. Bal oldalra írjuk a prímeket, és jobbra az összetett számokat. Először ide-oda ugrálnak. Nem fedezhetünk fel
semmilyen mintázatot. Használjunk egy modern
technikát az áttekintéshez! A trükk az Ulam spirál. Először felírjuk sorban az összes
számot egy növekvő spirál alakban. Azután kékre színezzük
a prímszámokat. Utána lekicsinyítjük,
hogy több millió számot lássunk. Előtűnik a prímszámok mintázata,
ami a végtelenségig folytatódik. Hihetetlen, de ennek
a mintázatnak a teljes struktúráját mind a mai napig nem oldották meg. Valaminek a nyomára bukkantunk. Most ugorjunk vissza Kr. e. 300-ig
az ókori Görögországba. Az alexandriai filozófus, Euklidesz
rájött, hogy minden szám besorolható e két kategória egyikébe. Azzal kezdte, hogy rájött,
bármely szám addig osztható, amíg eljutunk egy csoport
egyforma kisebb számhoz. A definíció szerint ezek a kisebb számok
mindig prímszámok. Így rájött arra, hogy minden szám kisebb prímszámokból épül fel. Képzeld el az összes szám világát úgy, hogy kihagyod a prímszámokat! Válassz ki egy tetszőleges
összetett számot, és bontsd fel! Mindig prímszámokat fogsz kapni. Euklidesz tudta, hogy minden szám
kifejezhető kisebb prímszámokkal. Ezekre építőkockákként
is gondolhatsz. Mindegy, melyik számot választod, ezek mindig felépíthetők
kisebb prímek összegeként. Ez ennek a felfedezésnek a gyökere, ami a számelmélet alaptétele
néven ismert: vegyél egy tetszőleges számot,
mondjuk 30-at, és keresd meg az összes prímszámot,
amivel egyenlően fel tudod azt bontani. Ezt prímtényezőkre bontásnak hívjuk. Így megkapjuk a prímtényezőket. Ebben az esetben a 30
prímtényezői a 2, a 3 és az 5. Euklidesz rájött, hogy megfelelő számszor
összeszorozva ezeket a prímtényezőket megkapjuk az eredeti számot. Ebben az esetben minden tényezőt
egyszer összeszorozva megkapjuk a 30-at. 2-szer 3-szor 5
a 30 prím tényezős felosztása. Úgy is tekintheted,
mint egy speciális kulcs, vagy kombináció. Másképp nem rakható össze a 30,
más prímszámok szorzataként. Ebből következik, hogy
minden számnak egy és csak egy
prímtényezős felosztása létezik. Ennek jó analógiája,
ha úgy képzeled el a számokat, mint egyedi zárakat. A zár egyedi kulcsa a prímtényezős felosztása. Két zárnak nincs azonos kulcsa. Nincs két olyan szám, aminek megegyezne
a prímtényezős felosztása.