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
Euler-féle Φ függvény
Számok oszthatóságának mérése. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Euler tovább vizsgálta
a számok tulajdonságait. Elsősorban a prímszámok
eloszlását vizsgálta. Definiált egy fontos függvényt, a Φ függvényt, ami egy szám felbonthatóságát méri. Ha adott egy szám, például N, akkor a Φ függvény megadja azon N-nél
kisebb vagy egyenlő egész számok számát, amelyeknek nincs közös osztójuk N-nel. Például, ha kíváncsiak
vagyunk Φ(8)-ra, megnézzük a számokat 1-től 8-ig, és megszámoljuk azokat az egészeket, amiknek a 8-cal nincs az
1-en kívüli közös osztója. Figyeld meg, a 6-ot nem számoljuk,
mert a 2 mindkét szám osztója, de az 1, 3, 5 és 7 mind számít,
mert csak az 1 a közös osztójuk. ezért Φ(8) értéke 4. Ami még érdekes, hogy a Φ függvény számítása
nehéz, kivéve egy esetet. Nézd meg ezt a grafikont! A Φ értékeket ábrázolja
1-től 1000-ig. Látsz valami megjósolható
mintázatot? A felül levő egyenes vonal
a prímszámokat jelöli. Mivel a prímszámoknak
nincs 1-nél nagyobb osztója, bármely P prímszámra
Φ értéke egyszerűen P-1. Φ(7) kiszámításához,
ami prímszám, számítani fog a 7-en kívül az összes
egész szám, mivel egyiknek se lesz
közös osztója 7-tel. Φ(7) értéke 6. Ha meg kell állapítani Φ(21377)
értékét, ami egy prímszám, csak ki kel vonni 1-et,
és megkapod az eredményt, 21376-ot. Bármelyik prímszám Φ értékét
könnyű kiszámolni. Ennek van egy érdekes következménye,
aminek az az alapja, hogy a Φ függvény relatív prím számok
esetén multiplikatív is. Ez azt jelenti, hogy
Φ(A·B) = Φ(A) · Φ(B). Ha tudjuk, hogy egy N szám
két prím szorzata, P1 · P2, akkor Φ(N) értéke a két prím Φ függvényértékének szorzata, azaz (P1-1) · (P2-1).