Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
5. lecke: Moduláris aritmetika- Mi a moduláris aritmetika?
- Modulo művelet
- Játék a modulóval
- Maradékosztály
- Kongruencia reláció
- Ekvivalence reláció
- Maradékos osztásra vonatkozó tétel
- Moduláris összeadás és kivonás
- Moduláris összeadás
- Moduláris kihívás (összeadás és kivonás)
- Moduláris szorzás
- Moduláris szorzás
- Moduláris hatványozás
- Gyors moduláris hatványozás
- Gyors moduláris hatványozás
- Moduláris inverz
- Az euklideszi algoritmus
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Moduláris inverz
Mit jelent egy művelet inverze?
Emlékszel? Ha egy számot megszorzol az inverzével, akkor 1-et kapsz eredményül. Az algebrából tudjuk, hogy:
- Egy A szám inverze 1/A, mivel A · 1/A = 1 (például 5 inverze 1/5)
- A 0-n kívül minden valós számnak van inverze
- Ha egy számot megszorzunk A inverzével, az ugyanazt jelenti, mintha elosztanánk A-val (például 10/5 megegyezik 10 · 1/5-tel)
Mi a modulo művelet inverze?
A moduláris aritmetikában nem létezik az osztás művelete. De létezik a multiplikatív inverz modulo C (a továbbiakban moduláris inverz).
- Az A (mod C) moduláris inverzét A^-1-el jelöljük.
- (A · A^-1) ≡ 1 (mod C), ami egyenértékű ezzel: (A · A^-1) mod C = 1.
- Csak a C-hez viszonyított relatív prímszámoknak (olyan számok, amelyeknek nincs C-vel közös prím osztója) van moduláris inverze (mod C).
Hogyan lehet megkeresni egy moduláris inverzet?
Az A (mod C) moduláris inverz megkeresésének egy egyszerű módja:
1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig.
2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1.
Vedd figyelembe, hogy B mod C csak 0 és C-1 közötti egész értékeket vehet fel, úgyhogy nem érdemes nagyobb értékekkel próbálkozni, mert redundáns lenne a számítás.
Példa: A=3, C=7
1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig .
3 · 0 ≡ 0 (mod 7)
3 · 1 ≡ 3 (mod 7)
3 · 2 ≡ 6 (mod 7)
3 · 3 ≡ 9 ≡ 2 (mod 7)
3 · 4 ≡ 12 ≡ 5 (mod 7)
3 · 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ MEGVAN AZ INVERZ!
3 · 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1
A 3 mod 7-nek a moduláris inverze 5, mivel 5 · 3 mod 7 = 1
Egyszerű!
Nézzünk még egy példát, ahol nem találunk inverzet!
Példa: A=2 C=6
1. lépés: számold ki A · B mod C-t minden B értékre 0-tól C-1-ig.
2 · 0 ≡ 0 (mod 6)
2 · 1 ≡ 2 (mod 6)
2 · 2 ≡ 4 (mod 6)
2 · 3 ≡ 6 ≡ 0 (mod 6)
2 · 4 ≡ 8 ≡ 2 (mod 6)
2 · 5 ≡ 10 ≡ 4 (mod 6)
2. lépés: A mod C moduláris inverze az a B érték lesz, ahol A · B mod C = 1
Nincs olyan B érték, ahol A · B mod C = 1. Ezért A-nak nincs moduláris inverze (mod 6) esetén.
Ez azért van így, mert 2 és 6 nem relatív prímszámok (a 2 mindkettőnek osztója).
Ez azért van így, mert 2 és 6 nem relatív prímszámok (a 2 mindkettőnek osztója).
Ez a módszer lassúnak tűnik...
Ennél van egy sokkal gyorsabb módszer az A (mod C) megkeresésére, amit a következő, az euklideszi algoritmusról szóló fejezetben fogunk tárgyalni.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.