- Gráfelméleti alapok
- Kuratowski gráfok, síkbarajzolhatóság
- Gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózati folyamok
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák, RSA kódolás
- Boole-algebra alapjai
Kongruenciák, RSA kódolás
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.
a) Bizonyítsuk be, hogy $a \equiv b \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b \cdot c \; \textrm{mod}\ m $
b) Bizonyítsuk be, hogy $a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \Rightarrow a \equiv b \; \textrm{mod}\ m $
a) Mi az utolsó két számjegye a $1789^{2046}$-nak?
b) Mi az utolsó két számjegye az alábbi számnak?
\( 39^{49^{59}} \)
Keressük azokat az $x$ egész számokat, amikre
a) \( 24x \equiv 13 \; \textrm{mod}\ 7\)
b) \( 13x \equiv 11 \; \textrm{mod}\ 120 \)
c) \( 13x \equiv 611 \; \textrm{mod}\ 120 \)
Keressük azokat az $x$ egész számokat, amikre
a) \( 59x \equiv 11 \; \textrm{mod}\ 120\)
b) \( 23x \equiv 63\; \textrm{mod}\ 43\)
Keressük azokat az $x$ egész számokat, amikre
a) \( 2x \equiv 14 \; \textrm{mod}\ 12 \)
b) \( 4x \equiv 36 \; \textrm{mod}\ 16\)
c) \( 14x \equiv 30 \; \textrm{mod}\ 18\)
d) \( 6x \equiv 10 \; \textrm{mod}\ 22\)
Oldjuk meg az alábbi Diofantoszi egyenleteket.
a) \( 3x+4y=13 \)
b) \( 13x+36y=56 \)
c) \( 4x+6y=13 \)
a) Milyen maradékot ad 66-tal osztva ez a szám?
\( 66^{63^{61}} \)
b) Milyen maradékot ad 1023-mal osztva ez a szám?
\( 1025^{1005} \)
c) Milyen maradékot ad 65-tel osztva ez a szám?
\( 138^{139} \)
Mi lesz az utolsó két számjegye ennek az alábbi számoknak?
a) \( 303^{404} \)
b) \( 33^{21^{34}} \)
Mi lesz az utolsó két számjegye ennek az alábbi számoknak?
a) \( 159^{161} \)
b) \( 49^{49^{50}} \)
Oldjuk meg az alábbi lineáris kongruenciákat.
a) \( 8x \equiv 30 \; \textrm{mod}\ 28\)
b) \( 2x \equiv 7\; \textrm{mod}\ 33\)
c) \( 47x \equiv 1\; \textrm{mod}\ 53\)
d) \( 9x \equiv 1\; \textrm{mod}\ 88\)
e) \( 8x \equiv 29\; \textrm{mod}\ 27\)
f) \( 32x \equiv 7\; \textrm{mod}\ 47\)
a) Egy $n$ egész szám 115-szöröse 110-zel nagyobb maradékot ad 344-gyel osztva, mint maga az $n$ szám. Milyen maradékot adhat $n$ 344-gyel osztva?
b) Az $n$ pozitív egész számra $43n-1$ utolsó két számjegye megegyezik $2n+2$ utolsó két számjegyével. Mi ez a két számjegy?
Mely egész számokra teljesül, hogy 7-tel osztva 2, 9-cel osztva 3 maradékot adnak?
