4. Számelméleti algoritmusok¶

Legnagyobb közös osztó¶

Definiáljuk a legnagyobb közös osztót, és az ahhoz szükséges fogalmakat!
Határozzuk meg a 90 és a 24 legnagyobb közös osztóját!

Prímtényezős felbontás

\[90 = 2 \cdot 3^2 \cdot 5, \quad 24 = 2^3 \cdot 3 \quad \Rightarrow \quad \text{lnko}(90, 24) = 6\]

Redukciós tétel

\[\begin{split}\text{lnko}(a, b) = \begin{cases} a, & \text{ ha } b = 0, \\ \text{lnko}(a - b, b), & \text{ ha } b \neq 0, \end{cases} \quad a \geq b.\end{split}\]

\[\text{lnko}(90, 24) = \text{lnko}(66, 24) = \text{lnko}(42, 24) = \text{lnko}(18, 24) = \text{lnko}(24, 18) =\]

\[\text{lnko}(6, 18) = \text{lnko}(18, 6) = \text{lnko}(12, 6) = \text{lnko}(6, 6) = \text{lnko}(0, 6) = \text{lnko}(6, 0) = 6\]

Mennyi lépésből fog állni lnko(1000000, 1) kiszámítása?
Milyen esetben adja a leggyorsabb, és a leglassabb megoldást?

Bináris LNKO¶

Definiáljuk a Bináris Legnagyobb Közös Osztó algoritmusát!
Számítsuk ki a 90 és 24 legnagyobb közös osztóját 10-es és 2-es számrendszeri felírással!

Euklideszi algoritmus¶

\[\begin{split}\text{lnko}(a, b) = \begin{cases} a, & \text{ ha } b = 0, \\ \text{lnko}(a, a \text{ mod } b), & \text{ ha } b \neq 0 \end{cases}\end{split}\]

a	b	a div b	a mod b
90	24	3	18
24	18	1	6
18	6	3	0
6	0		6

Az Euklideszi algoritmusnak mi a legrosszabb esete?

Lamé tétele¶

Ha \(a > b \neq 0\), és \(b < F_{k+1}\), akkor az Euklideszi algoritmus rekurzív hívásainak száma kevesebb, mint k.

Legfeljebb mennyi rekurzív hívás szükséges az lnko(283799, 76511) kiszámításához?

\[b = 76511 < F_{k+1}, \quad F_n = \text{Round}\left( \dfrac{1}{\sqrt{5}} \Phi^n \right), \quad 76511 = \dfrac{1}{\sqrt{5}} \Phi^n\]

\[\Rightarrow \quad n = \log_{\Phi} \sqrt{5} \cdot 76511 \approx 25.04076\]

\[F_{25} = 75025, \quad F_{26} = 121393\]

\[b < F_{25+1} \quad \Rightarrow \quad k = 25\]

Legfeljebb 24 rekurzív hívás szükséges!

A legnagyobb közös osztó reprezentációs tétele¶

\[d^{*} = \text{lnko}(a, b) = \min_{s \in L(a, b), s > 0} s = a \cdot x^{*} + b \cdot y^{*} = s^{*}\]

\(a\)	\(b\)	\(a \text{ div } b\)	\(a \text{ mod } b\)	\(d^{*}\)	\(x^{*}\)	\(y^{*}\)
133	157	0	133	1	-72	\(61 - (-72) \cdot 0 = 61\)
157	133	1	24	1	61	\(-11 - 61 \cdot 1 = -72\)
133	24	5	13	1	-11	\(6 - (-11) \cdot 5 = 61\)
24	13	1	11	1	6	\(-5 - 6 \cdot 1 = -11\)
13	11	1	2	1	-5	\(1 - (-5) \cdot 1 = 6\)
11	2	5	1	1	1	\(0 - 1 \cdot 5 = -5\)
2	1	2	0	1	0	\(1 - 0 \cdot 2 = 1\)
1	0		1	1	1	0

\[133 \cdot (-72) + 157 \cdot 61 = 1\]

Lineáris kongruencia egyenlet¶

Kongruencia: \(a \equiv b \mod n\)

\(a\) kongruens \(b\)-vel az \(n\) modulusra nézve, ha \(n\)-nel osztva \(a\) és \(b\) azonos maradékot ad.

Például: \(11 \equiv 7 \mod 4, \quad 712 \equiv 312 \mod 10\)

\[a \equiv b \mod n \quad \Leftrightarrow \quad n | a - b\]

Lineáris kongruencia egyenlet:

\[a \cdot x \equiv b \mod n, \quad x = ?\]

Két eset:

Nincs megoldás, ha \(\text{lnko}(a, n) \nmid b\)
Végtelen sok megoldás van, ha \(\text{lnko}(a, n) | b\)

alaprendszer:

\[x_0 = x^{*} \cdot \dfrac{b}{d^{*}} \mod n, \quad x_i = i \cdot \dfrac{n}{d^{*}} \mod n, (i = 1, \ldots, d^{*} - 1), \quad 0 \leq x_i < n\]

Oldjuk meg a \(84x \equiv 16 \mod 44\) egyenletet!
Ellenőrízzük a megoldást!

Multiplikatív inverz¶

Jelölése: \(a^{-1} \mod n\) (Az \(a\) multiplikatív inverze az \(n\) modulusra nézve.)

\(x = a^{-1} \mod n\), ha \(a \cdot x \equiv 1 \mod n\).

Ha \(\text{lnko}(a, n) \neq 1\), akkor nincs megoldás.
Ha \(\text{lnko}(a, n) = 1\), (tehát \(a\), \(n\) relatív prímek), akkor végtelen sok megoldás van, melynek alaprendszere: \(x_0 = x^{*} \mod n\)

Feladat:

Határozzuk meg 21 multiplikatív inverzét a 32-es modulusra nézve! \(21^{-1} \mod 32 = ?\)

\(a\)	\(b\)	\(a \text{ div } b\)	\(a \text{ mod } b\)	\(d^{*}\)	\(x^{*}\)	\(y^{*}\)
21	32	0	21	1	-3	\(2 - (-3) \cdot 0 = 2\)
32	21	1	11	1	2	\(-1 - 1 \cdot 1 = -3\)
21	11	1	10	1	-1	1 - (-1) cdot 1 = 2`
11	10	1	1	1	1	\(0 - 1 \cdot 1 = -1\)
10	1	10	0	1	0	\(1 - 0 \cdot 10 = 1\)
1	0		1	1	1	0

\[21^{-1} \mod 32 = 29\]

Moduláris hatványozás¶

\[a^b \mod n = ?\]

Határozzuk meg a \(98^{3114} \mod 150\) értékét!

\[3114_{10} = 110000101010_{2}\]

\(k\)	\(b_k\)	\(c^2 \mod n\)	\((c \cdot a) \mod n\)
11	1	\(1^2 = 1 \equiv 1\)	\(1 \cdot 98 = 98 \equiv 98\)
10	1	\(98^2 = 9604 \equiv 4\)	\(4 \cdot 98 = 392 \equiv 92\)
9	0	\(92^2 = 8464 \equiv 64\)
8	0	\(64^2 = 4096 \equiv 46\)
7	0	\(46^2 = 2116 \equiv 16\)
6	0	\(16^2 = 256 \equiv 106\)
5	1	\(106^2 = 11236 \equiv 136\)	\(136 \cdot 98 = 13328 \equiv 128\)
4	0	\(128^2 = 16384 \equiv 34\)
3	1	\(34^2 = 1156 \equiv 106\)	\(106 \cdot 98 = 10388 \equiv 38\)
2	0	\(38^2 = 1444 \equiv 94\)
1	1	\(94^2 = 8836 \equiv 136\)	\(136 \cdot 98 = 13328 \equiv 128\)
0	0	\(128^2 =16384 \equiv 34\)

\[98^{3114} \mod 150 = 34\]

Fermat-féle álprímteszt¶

Ha \(2^{p-1} \mod p = 1\) akkor \(p\) lehet prím. Ha \(2^{p-1} \mod p \neq 1\), akkor \(p\) biztosan nem prím.

Vizsgáljuk meg, hogy a 41 prímszám-e!

\[40_{10} = 101000_{2}\]

\(b_i\)	\(c^2 \mod 41\)	\(2 \cdot c \mod 41\)
1	\(1^2 \mod 41 = 1\)	\(2 \cdot 1 \mod 41 = 2\)
0	\(2^2 \mod 41 = 4\)
1	\(4^2 \mod 41 = 16\)	\(2 \cdot 16 \mod 41 = 32\)
0	\(32^2 \mod 41 = 40\)
0	\(40^2 \mod 41 = 1\)
0	\(1^2 \mod 41 = 1\)

\(2^{40} \mod 41 = 1\), így 41 lehet prím.

Vizsgáljuk meg, hogy a 42 prímszám-e!

\[41_{10} = 101001_{2}\]

\(b_i\)	\(c^2 \mod 41\)	\(2 \cdot c \mod 41\)
1	\(1^2 \mod 42 = 1\)	\(2 \cdot 1 \mod 42 = 2\)
0	\(2^2 \mod 42 = 4\)
1	\(4^2 \mod 42 = 16\)	\(2 \cdot 16 \mod 42 = 32\)
0	\(32^2 \mod 42 = 16\)
0	\(16^2 \mod 42 = 4\)
1	\(4^2 \mod 42 = 1\)	\(32 \mod 42 = 32\)

\(2^{41} \mod 42 = 32 \neq 1\), így a 42 nem lehet prím.

RSA algoritmus¶

Készítsük el a publikus és a privát kulcsot a következő adatok segítségével!

\[p = 23, q = 31 \quad \Rightarrow \quad n = p \cdot q = 713\]

\[e = 13, \quad f = (p - 1) \cdot (q - 1) = 660\]

\[d = e^{-1} \mod f = 13^{-1} \mod 660 = 457\]

publikus kulcs: \(P = (e; n) = (13; 713)\)
titkos kulcs: \(S = (d; n) = (457; 713)\)

Kódoljuk az \(M = 150\) üzenetet!

\[C = M^{e} \mod n = 150^{13} \mod 713 = 305\]

Dekódoljuk az előzőekben kódolt \(C = 305\) értéket!

\[M = C^{d} \mod n = 305^{457} \mod 713 = 150\]