2016, Diszkrét matematika

Diszkrét matematika 8. el˝oadás ´ MARTON Gy¨ ongyvér Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania [email protected]

2016, ˝ oszi f´ el´ ev

´ MARTON Gy¨ ongyv´ er

2016, Diszkr´ et matematika

Mir˝ol volt szó az elmúlt el˝oadáson?

a Fibonacci sz´ amsorozat a Fibonacci sz´ amrendszer beolvas´ asi lehet˝ oségek: a split és join f¨ uggvények pr´ımsz´ amok



Mir˝ol lesz szó?

Pr´ımsz´ amok, pr´ımtesztel˝ o algoritmusok oszt´ asi pr´ oba m´ odszere (trial division) Eratosztenész szit´ aja kongruenci´ ak modul´ aris hatv´ anyoz´ as maradékoszt´ alyok, maradékrendszerek a kis Fermat-tétel a kis-Fermat tételen alapul´ o pr´ımteszt az Euler f¨ uggvény



Algoritmusok Pythonban Pr´ımsz´ amok: azok az 1-nél nagyobb egész sz´ amok, amelyek nem oszthat´ oak, csak 1-el és o ¨nmagukkal. Rossz hatékonys´ ag´ u algoritmus: meghat´ arozzuk egy sz´ am oszt´ oinak sz´ am´ at, ha az egyenl˝ o kett˝ ovel akkor pr´ımsz´ am, m´ asképp nem. Oszt´ asi pr´ oba m´ odszere (trial division): sorra pr´ ob´ aljuk a p´ aratlan sz´ amokkal val´ o oszthat´ os´ agot. Az els˝ o oszt´ on´ al le´ all az algoritmus, azzal a kimenettel, hogy a sz´ am nem pr´ımsz´ am. Ha a tesztel˝ o sz´ am négyzetgy¨ okéig nem tal´ alunk oszt´ ot, akkor a sz´ am pr´ımsz´ am. Eratosztenész szit´ aja: kiz´ ar´ asos m´ odszerrel adott n-ig meghat´ arozza a pr´ımsz´ amok list´ aj´ at Miller-Rabin pr´ımteszt: egy adott p´ aratlan sz´ amr´ ol biztosan megtudja ´ allap´ıtani, hogy az o ¨sszetett, az azonban csak nagyon nagy val´ osz´ın˝ uséggel fogadhat´ o el, hogy a sz´ am pr´ım. ´ MARTON Gy¨ ongyv´ er


Eratosztenész szitája

Eratosztenész szit´ aj´ aval hat´ arozzuk meg 100-ig a pr´ımsz´ amokat: 1 11 21 31 41 51 61 71 81 91

2 12 22 32 42 52 62 72 82 92

3 13 23 33 43 53 63 73 83 93

4 14 24 34 44 54 64 74 84 94

5 15 25 35 45 55 65 75 85 95


6 16 26 36 46 56 66 76 86 96

7 17 27 37 47 57 67 77 87 97

8 18 28 38 48 58 68 78 88 98

9 19 29 39 49 59 69 79 89 99

10 20 30 40 50 60 70 80 90 100



Kivett¨ uk az 1-et és a 2-vel oszthat´ o sz´ amokat, a 2 marad: 1 11 21 31 41 51 61 71 81 91

2 12 22 32 42 52 62 72 82 92

3 13 23 33 43 53 63 73 83 93

4 14 24 34 44 54 64 74 84 94

5 15 25 35 45 55 65 75 85 95


6 16 26 36 46 56 66 76 86 96

7 17 27 37 47 57 67 77 87 97

8 18 28 38 48 58 68 78 88 98

9 19 29 39 49 59 69 79 89 99

10 20 30 40 50 60 70 80 90 100



Kivett¨ uk a 3-mal oszthat´ o sz´ amokat is, a 3 marad: 1 11 2 1 31 41 5 1 61 71 8 1 91

2 12 22 32 42 52 62 72 82 92

3 13 23 3 3 43 53 6 3 73 83 9 3

4 14 24 34 44 54 64 74 84 94

5

6

1 5 16 25 35 4 5 55 65 7 5 85 95


26 36 46 56 66 76 86 96

7 17 2 7 37 47 5 7 67 77 8 7 97

8 18 28 38 48 58 68 78 88 98

9 19 29 3 9 49 59 6 9 79 89 9 9


10 20 30 40 50 60 70 80 90 100


Kivett¨ uk az 5-tel oszthat´ o sz´ amokat is, az 5 marad: 1 11 2 1 31 41 5 1 61 71 8 1 91

2 12 22 32 42 52 62 72 82 92

3 13 23 3 3 43 53 6 3 73 83 9 3

4 14 24 34 44 54 64 74 84 94

5 1 5 2Z 5 Z 3Z 5 Z 4 5 5Z 5 Z 6Z 5 Z 7 5 8Z 5 Z 9Z 5 Z


6 16 26 36 46 56 66 76 86 96

7 17 2 7 37 47 5 7 67 77 8 7 97

8 18 28 38 48 58 68 78 88 98

9 19 29 3 9 49 59 6 9 79 89 9 9


10 20 30 40 50 60 70 80 90 100


Kivett¨ uk a 7-tel oszthat´ o sz´ amokat is, a 7 marad: 1 11 2 1 31 41 5 1 61 71 8 1 9Z 1 Z

2 12 22 32 42 52 62 72 82 92

3 13 23 3 3 43 53 6 3 73 83 9 3

4 14 24 34 44 54 64 74 84 94

5 1 5 2Z 5 Z 3Z 5 Z 4 5 5Z 5 Z 6Z 5 Z 7 5 8Z 5 Z 9Z 5 Z


6 16 26 36 46 56 66 76 86 96

7 17 2 7 37 47 5 7 67 7Z 7 Z 8 7 97

8 18 28 38 48 58 68 78 88 98

9 19 29 3 9 4 9 Z Z 59 6 9 79 89 9 9


10 20 30 40 50 60 70 80 90 100


¨ Osszesen marad 25, 1-nél nagyobb sz´ am, ezek a 100-n´ al kisebb pr´ımsz´ amok: 1 11 2 1 31 41 5 1 61 71 8 1 9Z 1 Z

2 12 22 32 42 52 62 72 82 92

3 13 23 3 3 43 53 6 3 73 83 9 3

4 14 24 34 44 54 64 74 84 94

5 1 5 2Z 5 Z 3Z 5 Z 4 5 5Z 5 Z 6Z 5 Z 7 5 8Z 5 Z 9Z 5 Z


6 16 26 36 46 56 66 76 86 96

7 17 2 7 37 47 5 7 67 7Z 7 Z 8 7 97

8 18 28 38 48 58 68 78 88 98

9 19 29 3 9 4 9 Z Z 59 6 9 79 89 9 9


10 20 30 40 50 60 70 80 90 100


Írassuk ki n-ig a pr´ımsz´ amokat: def erat(n): L = [True] * n L[0] = L[1] = False for i in range (2, n): if L[i] == True: print i, for j in range(i*i, n, i): L[j] = False




Hozzunk létre egy list´ at, amely tartalmazza n-ig a pr´ımsz´ amokat. def eratL(n): L = [True] * n L[0] = L[1] = False Lp = [] for i in range (2, n): if L[i] == True: Lp += [i] for j in range (i*i, n, i): L[j] = False return Lp




Hozzunk létre egy list´ at, amely tartalmazza n-ig a pr´ımsz´ amokat, csak a p´ aratlan sz´ amok felett végezz¨ uk a vizsg´ al´ od´ ast: def eratL_(n): L = [True] * n L[0] = L[1] = False Lp = [2] for i in range (3, n, 2): if L[i] == True: Lp += [i] for j in range (i*i, n, i): L[j] = False return Lp



Kongruenciák a sz´ amelmélet alapjait képezik, amelyet Gauss dolgozott ki, a 19. sz´ azadban, ax ≡ b (mod m) t´ıpus´ u egyenletek megold´ as´ ab´ ol indulunk ki, megjelenik a mindennapi életben: az o ´r´ ak (mod 12) vagy (mod 24) szerint, az év (mod 7) szerint m˝ uk¨ odik, stb., alkalmaz´ asi ter¨ ulet: adatbiztons´ ag, k´ odelmélet, Legyen m egy pozit´ıv egész sz´ am. Azt mondjuk, hogy a kongruens b-vel modulo m szerint, ha m | (a − b). Ezt a ≡ b (mod m)-el jel¨ olj¨ uk. Ellenkez˝ o esetben azt mondjuk, hogy a inkongruens b-vel modulo m szerint. ´ atalak´ıtva egyenletté: a ≡ b (mod m) akkor és csakis akkor, ha létezik egy k egész sz´ am, u ´gy hogy: a = b + km. Péld´ ak: 21 ≡ 3 (mod 9), mert 9 (21 − 3), hasonl´ oan: 4 ≡ −5 (mod 9) és 79 ≡ 7 (mod 9) 14 6≡ 5 (mod 12), mert 12 6 |(14 − 5) = 9 21 ≡ 3 (mod 9) ⇒ 21 = 3 + 2 · 9 ´ MARTON Gy¨ ongyv´ er


Kongruenciák Alaptulajdons´ agok reflex´ıv: ha a egy egész sz´ am, akkor a ≡ a (mod m), szimmetrikus: ha a, b egész sz´ amok és a ≡ b (mod m), akkor b ≡ a (mod m), tranzit´ıv: ha a, b, c egész sz´ amok és a ≡ b (mod m), b ≡ c (mod m), akkor a ≡ c (mod m), Aritmetikai m˝ uveletekkel kapcsolatos tulajdons´ agok: legyenek a, b, c, m egész sz´ amok, ahol m > 0 és a ≡ b (mod m). Ekkor fenn´ allnak a k¨ ovetkez˝ ok: a + c ≡ b + c (mod m), a − c ≡ b − c (mod m), a · c ≡ b · c (mod m), Az oszt´ as m˝ uveletére nem adhatunk anal´ og tulajdons´ agot.



Kongruenciák Az oszt´ assal kapcsolatos tulajdons´ ag: Legyenek a, b, c, m egész sz´ amok, ahol m > 0, d = lnko(c, m) és a · c ≡ b · c (mod m). Ekkor fenn´ all: a ≡ b (mod m/d). Péld´ ak: Legyen 14 ≡ 8 (mod 6) A kongruenci´ at nem tudjuk végigosztani 2-vel, mert nem igaz az, hogy 7 ≡ 4 (mod 6). A kongruenci´ at végigtudjuk osztani u ´gy 2-vel, hogy osztjuk a modulust is 2-vel, mert igaz, hogy lnko(2, 6) = 2, azaz fenn´ all: 7 ≡ 4 (mod 3) Legyen 42 ≡ 77 (mod 5) A kongruenci´ at végig tudjuk osztani 7-tel, u ´gy hogy osztjuk a modulust 1-el, mert igaz, hogy lnko(7, 5) = 1, azaz fenn´ all: 6 ≡ 11 (mod 5)



Kongruenciák

Az oszt´ assal kapcsolatos tulajdons´ ag: Péld´ ak: Legyen 50 ≡ 20 (mod 15) A kongruenci´ at nem tudjuk végigosztani 10-zel, mert nem igaz az, hogy 5 ≡ 2 (mod 15). A kongruenci´ at végig tudjuk osztani u ´gy 10-zel, hogy osztjuk a modulust is 5-tel, mert igaz, hogy lnko(10, 15) = 5, azaz fenn´ all: 5 ≡ 2 (mod 3) A kongruenci´ at végig tudjuk osztani u ´gy 5-tel, hogy osztjuk a modulust is 5-tel, mert igaz, hogy lnko(5, 15) = 5, azaz fenn´ all: 10 ≡ 4 (mod 3)



Kongruenciák

Tov´ abbi tulajdons´ agok: legyenek a, b, c, d, m egész sz´ amok, ahol m > 0, a ≡ b (mod m) és c ≡ d (mod m). Ekkor fenn´ allnak a k¨ ovetkez˝ ok: a + c ≡ b + d (mod m), a − c ≡ b − d (mod m), a · c ≡ b · d (mod m), an ≡ b n (mod m), ahol n pozit´ıv egész sz´ am.



Moduláris hatványozás

Mindenegyes négyzetre emelés ut´ an meghat´ arozzuk az oszt´ asi maradékot és ezzel az értékkel dolgozunk tov´ abb. Hat´ arozzuk meg 343 (mod 100) értékét: 3 32 34 38 316 332

≡ ≡ ≡ ≡ ≡ ≡

3 (mod 100) 9 (mod 100) 81 (mod 100) 61 (mod 100) 21 (mod 100) 41 (mod 100)

343 = 332 · 38 · 32 · 31 = 41 · 61 · 9 · 3 = 27 (mod 100)



Moduláris hatványozás

def modpow (x, n, m): res = 1 while n != 0: if n % 2 == 1: res = (res * x) % m x = (x * x ) % m n = n/2 return res



Maradékosztályok, maradékrendszerek a (mod n) szerinti oszt´ asi maradékok alapj´ an a sz´ amokat k¨ ul¨ onb¨ oz˝ o halmazokba csoportos´ıthatjuk ⇒ (mod n) szerinti maradékoszt´ alyok · · · ≡ −10 ≡ −5 ≡ 0 ≡ 5 ≡ 10 ≡ . . . · · · ≡ −9 ≡ −4 ≡ 1 ≡ 6 ≡ 11 ≡ . . . · · · ≡ −8 ≡ −3 ≡ 2 ≡ 7 ≡ 12 ≡ . . . · · · ≡ −7 ≡ −2 ≡ 3 ≡ 8 ≡ 13 ≡ . . . · · · ≡ −6 ≡ −1 ≡ 4 ≡ 9 ≡ 14 ≡ . . .

(mod 5) (mod 5) (mod 5) (mod 5) (mod 5)

a-nak (mod m) szerint a legkisebb nem negat´ıv oszt´ asi maradéka r , ha fenn´ all: a = q · n + r , ahol 0 ≤ r ≤ m − 1 teljes maradékrendszer: az a1 , a2 , . . . , am sz´ amok teljes maradékrendszert alkotnak m szerint, ha p´ aronként inkongruensek (mod m) szerint 0, 1, 2, ..., m − 1 teljes maradékrendszert alkotnak (mod m) szerint,



Maradékosztályok, maradékrendszerek

reduk´ alt maradékrendszer: a teljes maradékrendszer azon ai elemei amelyekre fenn´ all: lnko(ai , m) = 1. Péld´ ak (mod 6) szerint 1, 3, 5 reduk´ alt maradékrendszert alkotnak, (mod 6) szerint 0, 1, 2, 3, 4, 5 teljes maradékrendszert alkotnak,



A kis Fermat-tétel legjelent˝ osebb sz´ amelméleti eredmény nem ugyanaz, mint a nagy Fermat-tétel (x n + y n = z n )

1. tétel Ha x egy pr´ımsz´ am és a egy pozit´ıv egész sz´ am, u ´gy hogy 1 ≤ a ≤ x − 1, akkor ax−1 ≡ 1 (mod x). Példa: legyen x = 11, a = 3, ekkor fenn´ all: 310 = 59049 ≡ 1 (mod 11) m´ asfel˝ ol fel´ırhat´ ok a k¨ ovetkez˝ ok: 1·a=1·3≡3 2·a=2·3≡6 3·a=3·3≡9 4·a=4·3≡1 5·a=4·3≡4

(mod (mod (mod (mod (mod

11) 11) 11) 11) 11)

6 · a = 6 · 3 ≡ 7 (mod 11) 7 · a = 7 · 3 ≡ 10 (mod 11) 8 · a = 8 · 3 ≡ 2 (mod 11) 9 · a = 9 · 3 ≡ 5 (mod 11) 10 · a = 10 · 3 ≡ 8 (mod 11)

a fentiek alapj´ an hogyan bizony´ıtjuk a tételt? ´ MARTON Gy¨ ongyv´ er


A kis Fermat-tétel Ha egy x sz´ amra nem teljes¨ ul a fenti feltétel, akkor az egyértelm˝ uen o ¨sszetett sz´ am. Ha egy x sz´ amra teljes¨ ul a fenti feltétel, akkor az nem egyértelm˝ uen pr´ımsz´ am: vannak olyan o ¨sszetett sz´ amok amelyekre létezik olyan a sz´ am, hogy 1 ≤ a ≤ x − 1 és ax−1 ≡ 1 (mod x), ezeket a sz´ amokat a alap´ u Fermat-féle ´ alpr´ımeknek h´ıvjuk. Pl. 2-es alap´ u Fermat-féle ´ alpr´ım: 341, mert 2340 ≡ 1 (mod 341), ugyanakkor 341 = 11 · 31. Carmichael-sz´ amok: olyan o ¨sszetett sz´ amok amelyek esetében, minden a-ra, ahol lnko(a, n) = 1 és 1 ≤ a ≤ x − 1 fenn´ all ax−1 ≡ 1 (mod x). A legkisebb Carmichael-sz´ am: 561 = 3 · 11 · 17. A Carmichael-sz´ amok sz´ ama végtelen. Feladat: ellen˝ orizz¨ uk, hogy 561 Carmichael sz´ am. A kis-Fermat tétel az els˝ o kiindul´ asi pont a véletlensz˝ uen m˝ uk¨ od˝ o pr´ımtesztel˝ o algoritmusokhoz. ´ MARTON Gy¨ ongyv´ er


A kis-Fermat tételen alapuló pr´ımteszt Az algoritmus bemenete x, egy p´ aratlan sz´ am és egy t biztons´ agi paraméter. A t értékében azt adjuk meg, hogy h´ any a sz´ amot gener´ aljon véletlenszer˝ uen az algoritmus. A kimenet True ha az x sz´ am pr´ımsz´ am, figyelembe véve a t biztons´ agi paramétert, vagy False, ha a sz´ am o ¨sszetett. from random import randint from fractions import gcd def fermatT(x, t): for i in range(0, t): while True: a = randint(2, x - 1) if gcd(a, x) == 1: break #a gcd legnagyobb k¨ oz¨ os oszt´ ot sz´ amol, be´ ep´ ıtett f¨ uggv´ eny y = pow(a, x - 1, x) #a pow modul´ aris hatv´ any´ ert´ eket sz´ amol, be´ ep´ ıtett f¨ uggv´ eny if y != 1: return False return True ´ MARTON Gy¨ ongyv´ er


A kis-Fermat tételen alapuló pr´ımteszt Mi lesz az eredménye a k¨ ovetkez˝ o f¨ uggvényh´ıv´ asoknak, mennyi id˝ o sz¨ ukséges a v´ alaszhoz? >>> fermatT(561, 20) >>> fermatT(1615681, 20) >>> fermatT(1909001, 20) >>> fermatT(34857835975336692110070624231469883701559255636955113356 35708220200578192260458040143794181564548691304944895249930873708038 99356093770083239637007231768763806910240626478591473518028403152264 77238188282392855265632094297346142144217678505229299089264625307610 6034309993844531740085767636273327758260088939811, 10) Milyen sz´ amok 1909001, 1615681? ⇒ Charmichael sz´ amok 1909001 = 41 · 101 · 461 1615681 = 23 · 199 · 353



Az Euler-függvény

1. értelmezés Legyen n pozit´ıv egész sz´ am, ekkor az Euler-f¨ uggvény meghat´ arozza azokat a pozit´ıv egész sz´ amokat, amelyek nem nagyobbak mint n és relat´ıv pr´ımek n-nel. φ(n)-nel jel¨ olj¨ uk. Példa az Euler-f¨ uggvény értékeire, ha 1 ≤ n ≤ 12: n φ(n)

1 1

2 1

3 2

4 2


5 4

6 2

7 6

8 4

9 6

10 4


11 10

12 4

2016, Diszkrét matematika

Recommend Documents