Kongruenciák, Euler-Fermat tétel

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 \)

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$

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$

\( 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\)

Egy adott $m$ modulus esetén az $a$-val kongruens elemek halmazát az $a$ által reprezentált maradékosztálynak nevezzük.

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.

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) \)

$ a^{ \varphi(m)} \equiv 1 \; \textrm{mod}\ m $ ha $(a,m)=1$

$ a^p \equiv a \; \textrm{mod}\ p$ ha $p$ prím

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$.

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)$

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.