- Mátrixok és vektorok
- Egy kis geometria
- Vektorterek, független és összefüggő vektorok
- Lineáris egyenletrendszerek, mátrixok rangja és inverze
- Determináns, sajátérték, sajátvektor
- Lineáris leképezések
- Síkbeli és térbeli leképezések és mátrixaik
- Egyenletrendszerek optimális megoldása, pszeudoinverz
- Ortogonális mátrixok, Gram-Schmidt ortogonalizáció
- Mátrixok LU-felbontása és QR-felbontása
- Iterációs módszerek egyenletrendszerek megoldására
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Oszthatóság
- Euklideszi algoritmus, Diofantoszi egyenletek
- Kongruenciák, Euler-Fermat tétel
- Csoportok, gyűrűk, testek
Kongruenciák, Euler-Fermat tétel
Kongruencia
Ha $a$ és $b$ ugyanazt a maradékot adja $m$-mel osztva, akkor azt mondjuk, hogy $a$ és $b$ kongruensek modulo $m$, és ezt a tényt így jelöljük:
\( a \equiv b \; \textrm{mod}\ m \)
Kongruenciák tulajdonságai
Reflexív:
\( a \equiv a \; \textrm{mod}\ m \)
Szimmetrikus:
\( a \equiv b \; \textrm{mod}\ m \Rightarrow b \equiv a \; \textrm{mod}\ m\)
Tranzitív:
$a \equiv b \; \textrm{mod}\ m$ és $b \equiv c \; \textrm{mod}\ m \Rightarrow a \equiv c \; \textrm{mod}\ m $
Összefüggés összeadásra:
$ a \equiv b \; \textrm{mod}\ m$ és $c \equiv d \; \textrm{mod}\ m \Rightarrow a+c \equiv b+d \; \textrm{mod}\ m$
Összefüggés szorzásra:
$ a \equiv b \; \textrm{mod}\ m$ és $c \equiv d \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b\cdot d \; \textrm{mod}\ m$
Kongruencia vizsgálata
Legyenek $a$ és $b$ egész számok és $m$ pozitív egész szám.
Ekkor
$a \equiv b \; \textrm{mod}\ m$, ha $ m \mid a-b$
Műveletek kongruenciákban
\( a \equiv b \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \)
\( a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \Rightarrow a \equiv b \; \textrm{mod}\ m \quad (m,c)=1\)
Maradékosztály
Egy adott $m$ modulus esetén az $a$-val kongruens elemek halmazát az $a$ által reprezentált maradékosztálynak nevezzük.
Redukált maradékosztály
Egy mod $m$ modulus esetén az $m$-hez relatív prím elemekből álló maradékosztályokat redukált maradékosztálynak nevezzük.
A redukált maradékosztályok számát a $\varphi(m)$ számelméleti függvény írja le.
Euler-féle fí függvény
Az euler féle $ \varphi$ függvény azt adja meg, hogy hány $m$-nél nem nagyobb, $m$-hez relatív prím pozitív szám létezik.
Ha $p$ prím, akkor
\( \varphi (p) = p-1 \)
\( \varphi(p^{\alpha} = p^{\alpha} - p^{\alpha -1 } \)
És ha
\( m = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_n^{\alpha_n} \)
akkor
\( \varphi(m) = \left ( p_1^{\alpha_1} - p_1^{\alpha_1 - 1} \right) \cdot \dots \cdot \left ( p_n^{\alpha_n} - p_n^{\alpha_n - 1} \right) \)
Továbbá
\( \varphi(ab) = \varphi(a) \cdot \varphi(b) \)
Euler-Fermat tétel
$ a^{ \varphi(m)} \equiv 1 \; \textrm{mod}\ m $ ha $(a,m)=1$
Lineáris kongruenciák
A lineáris kongruenciák így néznek ki:
\( ax \equiv b \; \textrm{mod}\ m \)
És érdemes megjegyezni, hogy csak akkor oldhatók meg, ha $(a,m) \mid b$.
Lineáris kongruenciák megoldása
A lineáris kongruenciák így néznek ki:
\( ax \equiv b \; \textrm{mod}\ m \)
Megoldás csak akkor létezik, ha $(a,m) \mid b$.
A megoldás menete a következő:
1. lépés: Redukálunk
\( a_1 x \equiv b_1 \; \textrm{mod}\ m \)
2. lépés: Leosztunk $a_1$-gyel, de $b_1$-et lélekben fel kell erre készíteni
A megoldások száma: $(a,m)$
RSA kódolás
Az RSA lényege, hogy a titkosítás kulcsa nyilvános, vagyis azt bárki ismerheti. Csak a dekódolás kulcsa az, ami titkos.
Az alapötlete a következő:
Veszünk két jó nagy prímet, $p$-t és $q$-t amit csak mi ismerünk, ezek titkosak.
Elkészítjük az $N=p \cdot q$ számot és $\varphi(N)$-et, amit csak mi ismerünk.
Ha $p$ és $q$ többszázjegyű prímek, akkor $N$ prímfelbontása a jelenlegi számítógépekkel több ezer évig tartana, és így $\varphi(N)$ kiszámolása is lehetetlen.
Végül már csak egy dolog kell, egy $e$ kitevő, amire teljesül, hogy $ \left( e, \varphi(N) \right) = 1 $
Ezt követően jön a titkosítás.
A visszafejtéshez pedig az Euler-Fermat tétel kell, aminek segítségével megalkotjuk a $d$ megfejtő kulcsot.