Matematika | Diszkrét Matematika » Számelmélet

Számelmélet Ez a fejezet az egész számok számelméletébe vezet be. Az oszthatóság kérdésével foglalkozunk, majd a prímszámokról derítünk ki fontos tényeket, majd néhány fontosabb tételt említünk, melyek az egyik fontos gyakorlati alkalmazásnak: a nyilvános kulcsú titkosírás egyik módjának (RSA) alapját képezik. Ebben a fejezetben kizárólag egész számokkal, sőt, többnyire csak természetes számokkal foglalkozunk, ezért a definíciók, tételek kimondásánál ezt mindig alapértelmezésnek tekintjük akkor is, ha külön nem hangsúlyozzuk. Maradékos osztás, oszthatóság Az egész számok köréből az összeadás, kivonás, szorzás nem vezet ki, ám az osztás igen, ezt nem használhatjuk, ha kizárólag egész számokkal szeretnénk foglalkozni. Bevezetünk helyette egy másik műveletet, az ún maradékos osztást Definíció: Maradékos osztás Adott két egész szám: a, b. Ha a = bq + r (0 ≤ r < b ) , akkor q a hányados, r az

osztási maradék. Jelölés: a:b=q (maradt r) Adott a és b esetén a fenti feltételek mellett r és q egyértelmű. Például 15:4=3 (maradt 3), (-15):4=4 (maradt 1). (Utóbbi esetben a (-15)-nél nem nagyobb 4gyel osztható számok közül a legnagyobb a (-16), ezért 4 a hányados) Alapvető fontosságú reláció az oszthatóság, melyre további fontos fogalmaink épülnek: Definíció: Oszthatóság Ha a maradék nélkül (r=0) osztható b-vel, akkor azt mondjuk, hogy „b osztója a-nak”. Jelölés: b | a (Vagyis: b | a ⇔ ∃k : a = kb ) Az oszthatóság tehát egy reláció, melyről belátható, hogy reflexív, antiszimmetrikus és tranzitív (ily módon tehát (részleges) rendezés). A következő apró tételek az oszthatóság és a műveletek kapcsolatára vonatkoznak: Tétel: x | a x | a + b ⇒ x | b  x | a − b x | a ⇒ x | ka Kiemelt fontosságúak az olyan elemek, melyek minden másnak osztói. Definíció: Egység Az ε számot egységnek

mondjuk, ha ∀a : ε | a Tétel: Az egész számok körében két egység van: +1;-1. Tehát pontosan e két szám osztója minden egész számnak. Az oszthatóság által felvethető másik fontos kérdés: vannak-e olyan elemek, melyek nem oszthatók mással (természetesen az egységeken kívül)? Ilyenek vannak, ezek a felbonthatatlan számok. Definíció: Felbonthatatlan szám Az f számot felbonthatatlannak nevezzük, ha a triviálisakon (egységek, önmaga) kívül más osztója nincs, vagyis: f | ab ⇒ a = ε vagy b=ε Az egész számok körében ezzel ekvivalens fogalom a prímszám fogalma, pedig a definíciója más: Definíció: Prímszám A p számot prímnek nevezzük, ha p | ab ⇒ p | a vagy p | b Ez a definícióban szereplő tulajdonság nem okvetlenül egyezik meg a felbonthatatlanság definíciójánál olvasottakkal, ám fontos szerepet kap egyes bizonyításoknál. Bebizonyítható, hogy az egész számok körében a prímszám és a felbonthatatlan szám

fogalma ugyanaz. Más halmazokban (egész számok részhalmazai, egyéb absztrakt halmazok (pl polinomok)) is lehetséges az oszthatóság fogalmát definiálni, lehet beszélni prímekről és felbonthatatlanokról, de ekvivalenciájuk nem mindig igaz. Tétel: Felbonthatatlan és prím ekvivalenciája Az egész számok halmazán a felbonthatatlan és a prím fogalma ekvivalens. Erre alapozva a továbbiakban ezt a különbséget nem hangsúlyozzuk, többnyire a prím fogalmat fogjuk használni – már csak rövidsége okán is. Definíció: Összetett szám A nem felbonthatatlan számokat összetett számoknak nevezzük. Az összetett számok nyilván nemtriviális tényezők szorzatára bonthatók, ha azok nem prímek (felbonthatatlanok), akkor azok is, és így tovább. Felmerül a kérdés, mi egy ilyen eljárás vége Erre ad választ a mindannyiunk által régóta ismert, azonban egyáltalán nem magától értetődő, bizonyításra szoruló tétel: Tétel: Számelmélet

alaptétele (SZAT) Az egész számok lényegében egyértelműen bonthatók prímek szorzatára, eltekintve a tényezők sorrendjétől és az egységszeresektől. Itt arról van szó, hogy adott prímtényezős felbontás esetén a szorzatban a tényezőket tetszés szerint cserélgethetjük, vagy közülük bármelyiket megszorozhatjuk valamelyik egységgel, ezeket a módosulatokat nem tekintjük lényegesen különbözőnek. Ettől eltekintve a felbontás egyértelmű A SZAT bizonyítását itt mellőzzük, de megemlítjük, hogy a hozzá vezető úton fontos láncszem az ún. euklideszi algoritmus Mivel ez elméleti jelentősége mellett önmagában is hasznos gyakorlati módszer, részletesebben tárgyaljuk A módszer maga egy igen jó és gyors eljárás két szám legnagyobb közös osztójának megkeresésére – a prímtényezős felbontás elvégzése nélkül! Bevezetünk két újabb fogalmat: Definíció: Legnagyobb közös osztó (LNKO) Két szám legnagyobb közös

osztóján a mindkettőt maradék nélkül osztó számok közül a legnagyobbat értjük. Jelölés: (a,b) Ehhez hasonló fogalom a kitüntetett közös osztó, melyet máshogy definiálunk, de az ekvivalencia igazolható: Definíció: Kitüntetett közös osztó (KKO) Két szám kitüntetett közös osztóján azt a közös osztót értjük, melynek minden további közös osztó is osztója. Tétel: A legnagyobb közös osztó (LNKO) és a kitüntetett közös osztó (KKO) fogalma ekvivalens. Természetesen úgy értve, hogy az egységszeres erejéig, hiszen a KKO negatív is lehet. Lássuk az euklideszi algoritmust! Pl. 30 és 12 LNKO-ját szeretnénk megkeresni: 30 12 6 0 Az történt, hogy 30-at elosztottuk 12-vel és leírtuk az osztási maradékot: 6. Utána a 12-t osztottuk 6-tal, de az maradék nélkül megvan: a maradék 0 E z tarthatott volna tovább is, de előbb-utóbb mindig végetér 0-val; a LNKO a 0 előtti utolsó maradék, most 6. Lássuk be, hogy ez tényleg a

LNKO – illetve pontosabban hogy KKO, de mint láttuk, ugyanaz! Az algoritmus maradékos osztások sorozatából áll. Ezt addig ismételgetjük, amíg nem kapunk egyszer 0 maradékot. Ez mondjuk az n lépésben bekövetkezik: a = bq1 + r1 b = r1q2 + r2 r1 = r2 q3 + r3 r2 = r3 q4 + r4 . rn−3 = rn−2 qn−1 + rn−1 rn−2 = rn−1qn (+ rn ) rn = 0 Állítás: az algoritmus mindig véges számú lépésben végetér. Ez azért van így, mert az osztási maradék szükségszerűen kisebb az osztónál (mert különben még egyszer kikerülne belőle az osztó). Ráadásul az algoritmus nagyon gyors, mert belátható, hogy a maradék még legszerencsétlenebb esetben is kétlépésenként legalább megfeleződik, de gyakran ennél gyorsabban is fogy. Állítás: rn−1 KKO, vagyis egyrészt maga is közös osztó, másrészt neki minden közös osztó osztója is. 1.) rn−1 rn−2 = rn−1qn ⇒ rn−1 | rn−2   ⇒ rn−1 | rn−3 rn−3 = rn−2 qn−1 + rn−1  rn−4

= rn−3 qn−2 + rn−2   közös osztó. A fenti egyenletek szerint ugyanis: rn−1 | rn−2  ⇒ rn−1 | rn−4  rn−1 | rn−3  . Lépésről-lépésre visszafelé haladva kiderül, hogy rn−1 | b , rn−1 | a , vagyis közös osztó. 2.) rn−1 -nek minden egyéb közös osztó osztója, vagyis c | a  ⇒ c | rn−1 . Most az elejéről indulc | b c|a   c|b  ⇒ c | r1 a = bq1 + r1  c|b c | r1    ⇒ c | r2 va a következőt látjuk: b = r1q2 + r2  c | r1   c | r2  ⇒ c | r3 r1 = r2 q3 + r3  . Lépésről-lépésre haladva kiderül, hogy valóban c | rn−1 . Természetesen a módszer közvetve alkalmas a legkisebb közös többszörös megkeresésére is. Definíció: Legkisebb közös többszörös (LKKT) Két szám legkisebb többszörösén azon (pozitív) számok közül a legkisebbet értjük, melynek mindkettő osztója. Közismert, hogy két szám LNKO-jának és LKKT-ének szorzata a számok

szorzatát adja: Tétel: LNKO (a, b) ⋅ LKKT (a, b) = a ⋅ b Emlékezzünk rá, hogy az LNKO ill. LKKT prímtényezős felbontásból való meghatározásához éppen ellenkezőleg válogatjuk a prímtényezőket! A szorzatban éppen a két szám prímtényezői együtt szerepelnek Prímszámok A prímszámok a SZAT értelmében valamiféle „építőkövekként” működnek, kiemelt fontosságúak. A prímek ellentettje is prím, de mi többnyire a pozitív (természetes) prímekről fogunk beszélni. A prímek halmaza az egyik legkönnyebben definiálható, mégis rendkívül érdekes szerkezetű struktúra. Ebben a szakaszban a prímszámok tulajdonságairól, számukról, elhelyezkedésükről ejtünk szót. Az első fontos kérdés, hogy hány prímszám van? A kérdésre a válasz régóta ismert, a bizonyítás már Euklides-nél is szerepel. Tétel: Végtelen sok prímszám van. Bizonyítás: Indirekt tegyük fel, hogy véges sok prímszám van: p1 , p2 ,. pn Vegyük ezek

szorzatát: n A = p1 p2 . pn = ∏ pi Mivel ∀pi | A ⇒ ∀pi /| A + 1 Tehát A+1- nek nem osztója az i =1 eddigi egyik prím sem, pedig a SZAT szerint – ha összetett – azok között kellene osztójának lenni. Ezek szerint újabb prímet találtunk, ami ellentmond az indirekt feltételünknek Vagyis az indirekt feltétel ellenkezője lehet csak igaz Miután kiderült, hogy végtelen sok prím van, ezek elhelyezkedését fogjuk vizsgálni. Először is lássunk egy – szintén ókorból származó – módszert, mely képes prímeket generálni. Ez az ún eratosztenészi szita Írjuk fel sorban a számokat, de az egyet rögtön vegyük ki, mert az az egység. A 2 az első prím, a többszöröseit kihúzzuk: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 A „talpon maradók” közül kiválasztjuk az elsőt, ez a következő prím, a 3, majd kihúzzuk a többszöröseit: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 (Lehetséges, hogy egy számot

többször húzunk ki, ez nem baj.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 A „szitán” nyilván csak azok a számok maradhatnak fenn, amelyek másoknak nem többszörösei, vagyis nincsenek valódi osztóik: ezek a prímek. Az eljárásból érződik, hogy az egyre nagyobb számok egyre nagyobb „veszélyben” vannak; a rostálás során egyre többször „süvít el” mellettük a számokat kiejtő eljárás. Statisztikusan a nagyobb számoknak kevesebb esélyük van „prímnek maradni”. Valóban van egy tendencia, mely szerint a prímszámok a nagyobb számok között egyre „ritkulnak”. Ezt látszik alátámasztani a következő tétel: Tétel: A prímek közti hézag nem korlátos. Ez azt jelenti, hogy elég messze menve bármekkora hézagot lehet találni két szomszédos prím között. Bizonyítás: Mutatunk egy eljárást, mellyel bármely kívánt hézaghoz megadható az intervallum: Azt szeretnénk, hogy n darab szomszédos szám között ne

legyen prím. Állítás: ha (n+1)!+2-től (faktoriális) (n+1)!+n+1 ig vesszük a számokat, akkor ezek között egyik sem prím. (Ez pontosan n darab szomszédos számot jelent) Mivel (n+1)! az összes szám szorzata 1-től n+1-ig, ezért minddel osztható. Ezután persze az ehhez mért differencia (2 és n+1 közti szám) is osztható valamelyikkel, tehát az összeg is: (n+1)!+2 osztható 2-vel (n+1)!+3 osztható 3-mal (n+1)!+4 osztható 4-gyel (n+1)!+n+1 osztható n+1-gyel Az (n+1)!+1-et azért ugrottuk át, mert az 1-gyel való oszthatóság semmitmondó, semmi nem következik belőle, az nem biztos, hogy nem prím. Ez a tétel nem jelenti azt, hogy a hézag monoton növekedne, és még azt sem, hogy a végtelenbe tartana. Egyáltalán nincs rá garancia, hogy egy akármekkora hézag után ne legyen ismét kisebb. Sőt! A prímszámokkal kapcsolatos egyik legérdekesebb, máig megoldatlan sejtés a következő: Sejtés: Ikerprím-sejtés Végtelen sok ikerprím van. Az

„ikerprím” azt jelenti, hogy két szomszédos páratlan szám mindegyike prím (pl. 5-7; 1113; 17-19) Ez jelenleg egy sejtés, nem tétel, ugyanis a mai napig sem cáfolni, sem igazolni nem sikerült. Mindazonáltal nagyon úgy tűnik, hogy igaz Két szomszédos szám egyike biztos prím, három szomszédos páratlan szám közül pontosan egyik 3-mal osztható. Tehát hármasiker csak egy van: 3-5-7. Tehát miközben a hézag bármilyen nagyra nőhet, úgy tűnik mindig újra és újra lecsökken 2re! A legnagyobb ismert ikerprím-pár jelenleg: 33218925 ⋅ 2169690 ± 1 . Ezek 51090 jegyű számok Összességében tehát úgy gondoljuk, hogy a prímek statisztikusan ritkulnak, de a sűrűségükben egy véges intervallumon belül nagy anomáliák lehetnek. Lehet-e mondani mégis valami megfoghatót? Egyrészt el lehet mondani, hogy a prímszámok viszonylag „sűrűn”, „sokan” vannak. Erre utal a következő: Tétel: A prímszámok reciprokösszegének sora ( ∑ Vagyis

1 ) divergens. pi 1 1 1 1 1 1 1 + + + + + + + . = ∞ 2 3 5 7 11 13 17 Önmagában végtelen sok szám (reciprokának) összeadása még lehet véges, ha elég gyorsan tartanak nullához az összeadandó értékek. Például a négyzetszámok reciprokösszege véges, 2-höz tart. Ha nem így történik, akkor az összeadandók „sokan vannak” A sűrűség-eloszlásra bizonyos mértékű egyenletességet biztosít a következő törvényszerűség: Tétel: Csebisev tétele Egy szám és kétszerese között mindig van prím. Ez sugall valami olyasmit, hogy adott nagyságrendű számok között nagyon extrém módon nem ritkulhatnak meg. Létezik egy statisztikai jellegű tétel, mely mennyiségi becslést képes adni a prímek számára. Tétel: (nagy) Prímszámtétel: Ha Π (x) a prímek száma x-ig, akkor lim n ∞ x Π ( x) . = 1 , vagyis Π ( x) ≈ ln x x / ln x Ez a tétel bizonyított, de nyilván csak statisztikailag igaz, mert egy folytonos függvény természetesen

nem képes leírni a fentebb is taglalt szabálytalan változásokat. Vizsgáljuk meg kicsit, mit is állít ez a tétel! Nem túl nagy számokra az egyenkénti prímkeresés módszerével pontosan össze lehet számolni, hány darab van, mejd ezt összevethetjük a közelítő formula által adott (kerekített) értékkel: x tényleges Π (x) x ln x 100 1000 10000 25 168 1229 22 145 1086 100000 9592 8686 1000000 78498 72382 10000000 664579 620421 100000000 5761455 5428681 1000000000 50847534 48254942 Láthatjuk, hogy nagyságrendileg meglehetősen együtt vannak, és ez egyre nagyobb értékekre egyre inkább igaz. Becsüljük meg a prímszámtétel segítségével, milyen sűrűn vannak prímek a 1050 nagyságrendű (50 jegyű) számok között! A prímek száma 1050-ig: Π (1050 ) = 8.69 ⋅ 10 47 A prímek száma 1.1*1050-ig: Π (1.1 ⋅ 1050 ) = 955 ⋅ 10 47 A különbség: 8.61 ⋅ 10 46 (ennyi prím van a vizsgált tartományban 1049 darab szám között)

Az arányt osztással számítva az adódik, hogy átlagosan kb. minden 116 szám prím! Ez azért döbbenetes, mert itt akkora számokról van szó nagyjából, mint ahány atomból a Föld anyaga áll! Ehhez képest nagyon sűrűnek kell tekinteni, hogy szinte minden századik szám prím, hogy még itt is ennyien elkerülik Eratosztenész rostáját! Ha a 100 jegyű számok közé megyünk, még ott is 231-et ad a fenti számítás! A ma ismert legnagyobb prímek a Mersenne-prímek. Definíció: Mersenne-prím A p = 2 k − 1 alakban felírható prímeket Mersenne-prímeknek nevezzük. Nem arról van szó, hogy az ilyen alakú számok mindig prímek, de bizonyos tesztelhető esetekben igen. Ilyenkor egyébként szükségszerűen a kitevő is prím A Mersenne-prímeknek érdekes kapcsolatuk van az ún tökéletes számokkal A jelenleg ismert legnagyobb (Mersenne-)prím: 213466917 − 1 . Ez egy 4053946 jegyű szám és 2001. novemberében találták Számelméleti függvények

Két, egész számokhoz egész számokat rendelő számelméleti függvényt említünk meg: d (n) , ϕ (n) . Előbbi egy szám osztóinak a számát mutatja meg, utóbbi a számhoz relatív prímek számát. Mindkettőre adható explicit formula, melyek azonban a számok prímtényezős felbontását használják Tehát feltételezzük: hogy a szám prímtényezős felbontása az alábbi ún kaα α nonikus alakban ismert: n = p1 1 p2 2 . pr αr r = ∏ pi αi (pl. 60 = 2 2 ⋅ 3 ⋅ 5 ) i =1 d (n) – n osztóinak száma Tétel: r d (n) = (α1 + 1)(α 2 + 1).(α r + 1) = ∏ (α i + 1) i =1 Pl. d (12) = (2 + 1)(1 + 1)(1 + 1) = 3 ⋅ 2 ⋅ 2 = 12 (1,2,3,4,5,6,10,12,15,20,30,60) A magyarázat egyszerűen az, hogy a szám osztóit a prímtényezőiből állíthatjuk össze. Minden prímtényező beválasztható a szorzatba annyiféleképp, ahányadik hatványon szerepel, és plusz egy lehetőségként megvan az, hogy egyáltalán nem választjuk be (0. hatványon

szerepeltetjük) A képlet egyszerűen ezen kombinációs lehetőségek száma Érdemes megfigyelni, hogy ez csupán a kitevőktől függ, vagyis a prímtényezők sokféleségétől és fajtánkénti mennyiségétől. A másik függvény az adott számhoz relatív prím természetes számok számát adja. Definíció: Relatív prímek Két számot egymáshoz relatív prímnek mondunk, ha felbontásuk nem tartalmaz közös prímtényezőt, vagyis LNKO-juk 1. ϕ (n) – n-hez relatív prímek száma n-ig Tétel:  ϕ (n) = n1 − Magyarázat:  r  1  1   1  1 1 − .1 −  = n∏ 1 −  p1  p2   pr  pi  i =1  Egy p prímhez minden nála kisebb szám relatív prím, tehát ϕ ( p) = p − 1 . Egy p k prímhatványhoz minden nála kisebb relatív prím, p többszöröseit kivéve. Ez éppen a  pk 1 pk . Vagyis ϕ ( p k ) = p k − = p k 1 −  . Mivel belátható, p p p

 hogy relatív prímekre a függvény multiplikatív, vagyis (a, b) = 1 ⇒ ϕ (ab) = ϕ (a)ϕ (b) , így a kanonikus alakban szereplő prímhatványok szorzatára alkalmazva: r     1   1  1  1  1   1  1 ϕ (n) = p1 1 −  p2 1 − . pr 1 −  = p1 p2 pr 1 − 1 − 1 −  = n∏ 1 − p1   p2  pr  p1  p2   pr  pi i =1     vizsgált számok p-ed része: Kongruenciák A kongruencia egy reláció, mely szoros kapcsolatban van az oszthatósággal. Definíció: Kongruencia Két számot pontosan akkor mondunk kongruensnek, ha adott m modulussal (osztóval) ugyanazt az osztási maradékot adják. Jelölés: a ≡ b mod m , vagy a ≡ b(m) a ≡ b mod m ⇔ m | a − b Például 28 ≡ 33 mod 5 , mert 5-tel osztva egyaránt 3-at adnak maradékul, vagyis a különbségükben megvan az 5, vagyis 5 osztja a különbségüket. Tétel: A

kongruencia ekvivalencia-reláció (reflexív, szimmetrikus, tranzitív). Be kell látnunk az ekvivalencia-relációtól megkövetelt három tulajdonságot: 1.) reflexív: ∀a : a ≡ a mod m ⇔ m | a − a = 0 , ez pedig nyilván igaz 2.) szimmetrikus: ∀a, b : a ≡ b mod m ⇒ m | a − b ⇒ m | b − a = −(a − b) ⇒ b ≡ a mod m 3.) tranzitív: a ≡ b mod m ⇒ m | a − b  ∀a, b, c :   ⇒ m | (a − b) + (b − c) ⇒ m | a − c ⇒ a ≡ c mod m b ≡ c mod m ⇒ m | b − c  Ha egy halmazon ekvivalencia-relációt értelmeztünk, akkor az a h almazt ekvivalenciaosztályokra bontja. Adott m modulus mellett m-féle osztási maradék létezhet (0m-1) Minden egész szám egyértelműen sorolható be pontosan egyikbe    Definíció: mod m maradékosztályok Az m modulusú kongruencia által definiált ekvivalencia-osztályokat mod m („modulo m”) maradékosztályoknak nevezzük. Definíció: Teljes maradékrendszer (TMR) Ha minden

mod m maadékosztályból veszünk egy reprezentánst, ezek összessége a teljes maradékrendszer. Az egyazon maradékosztályba tartozó számok a kongruenciákban hasonló módon viselkednek, lényegében mindegy, hogy melyik elemével reprezentáljuk, egy szám kicserélhető egy vele kongruenssel. A gyakorlatban célszerű minél kisebb reprezentánst választani, hogy könynyebb legyen a számolás A maradékrendszer (és a maradékosztályok) közül fontosak azok, melyek a modulushoz relatív prímek. (Ezek hasonlóan fontos szerepet töltenek be a maradékosztályok között, mint a prímek az egész számok körében.) Definíció: Redukált maradékosztályok A mod m maradékosztályok közül azokat, melyek elemei a modulushoz relatív prímek, redukált maradékosztályoknak nevezzük. Egy maradékosztályon belüli elemek a modulushoz bizonyíthatóan ugyanúgy viszonyulnak, vagyis vagy mind relatív prím a modulushoz, vagy egyik sem. Így lehet beszélni erről mint

globális osztály-tulajdonságról. Definíció: Redukált maradékrendszer (RMR) Ha minden mod m redukált maradékosztályból veszünk egy reprezentánst, ezek összessége a redukált maradékrendszer. A redukált maradékosztályok száma természetesen az m-hez relatív prímek számával egyezik meg: ϕ (m) . Vegyünk egy teljes maradékrendszert! Ha ennek minden eleméhez hozzáadjuk ugyanazt a számot, vagy minden eleméből kivonjuk ugyanazt a számot, továbbra is teljes maradékrendszert kapunk. Pl m=10: n≡ n+5≡ n−2≡ n+3≡ 0 5 8 3 1 6 9 4 2 7 0 5 3 8 1 6 4 9 2 7 5 0 3 8 6 1 4 9 7 2 5 0 8 3 6 1 9 4 7 2 n≡ n⋅5 ≡ n⋅2 ≡ n⋅3 ≡ 0 0 0 0 1 5 2 3 2 0 4 6 3 5 6 9 4 0 8 2 5 5 0 5 6 0 2 8 7 5 4 1 8 0 6 4 9 5 8 7 Igaz-e ez szorzásra? Látjuk, hogy szorzásra nem okvetlenül igaz, pl. a maradékrendszer 5-tel vagy 2-vel való végigszorzása nem eredményez teljes maradékrendszert A 3-mal való szorzás viszont teljes maradékrendszert

ad. Ez kapcsolatban lehet azzal, hogy a 3 pr ím, de igazából az a lényeg, hogy a modulushoz (10) relatív prím. Tétel: Legyen a1 , a2 ,., am teljes maradékrendszer mod m Ekkor (k , m) = 1 ⇔ ka1 , ka2 ,., kam is teljes maradékrendszer mod m Vagyis arról van szó, hogy pontosan a modulushoz relatív prímmel végigszorzva lehet a maradékosztályok egy permutációját előállítani. Vegyünk egy redukált maradékrendszert, vagyis a modulushoz relatív prím maradékosztályokból válasszunk reprezentánsokat. Pl m=10 ismét: n≡ n−2≡ n+3≡ 1 3 7 9 9 1 5 7 4 6 0 2 Láthatóan nem kapunk redukált maradékrendszert, hiszen – a teljes maradékrendszertől eltérően – ez szabálytalanul hézagos, tehát egy lineáris eltolás nem viszi önmagába. A modulus többszöröseivel való eltolás persze igen. Nézzük a szorzást: n≡ n⋅2 ≡ n⋅3 ≡ 1 3 7 9 2 6 4 8 3 9 1 7 Fentebbihez hasonló tételt lehet itt is megfogalmazni: Tétel: Legyen a1 , a2

,., aϕ ( m ) redukált maradékrendszer mod m Ekkor (k , m) = 1 ⇔ ka1 , ka2 ,., kaϕ ( m ) is redukált maradékrendszer mod m Vagyis arról van szó, hogy pontosan a modulushoz relatív prímmel végigszorozva lehet a redukált maradékosztályok egy permutációját előállítani. Mi történik, ha egy a számot egy adott modulus mellett hatványozni kezdünk (m=10)? n= 2n ≡ 3n ≡ 7n ≡ 1 2 3 7 2 4 9 9 3 8 7 3 4 6 1 1 5 2 3 7 6 4 9 9 7 8 7 3 8 6 1 1 9 2 3 7 10 4 9 9 Némely hatványok mod m maradéka között nem szerepel az 1, másoknál szerepel, és a sorban éppen a redukált maradékrendszerek képviseltetik magukat. Az ismétlődési periódus hossza m=10 esetén 4. Ezzel kapcsolatban mond valamit a következő tétel: Tétel: Euler-Fermat-tétel, vagy Euler kongruenciatétele (a, m) = 1 ⇒ a ϕ ( m ) ≡ 1mod m Vagyis arról van szó, hogy a modulushoz relatív prím alap hatványozásával elő lehet állítani az 1-es maradékot, méghozzá a ϕ (m)

-edik hatvány pont ilyen. (Ez nem jelenti azt, hogy ez az első ilyen és előbb nem lehet a hatvány értéke 1, de ez biztos.) A bizonyítástól eltekintünk, viszont megemlítjük fenti tétel egyik speciális esetét: Tétel: (kis) Fermat-tétel Ha p prím, akkor (a, p ) = 1 ⇒ a p −1 ≡ 1mod p ⇔ a p ≡ a mod p Ez az előbbi tétel speciális esete m=p prímre, hiszen prímek esetén ϕ ( p ) = p − 1 . Léteznek az egyenletek mintájára kongruenciával felírt összefüggések, melyekben alkalmas ismeretlent keresünk. A részletek elemzése nélkül megemlítünk egy egyszerűbb típust, a lineáris kongruenciát: ax ≡ b mod m Ebben a és b adottak, keressük az alkalmas x-et. (a,b)= 1 esetben megoldást szolgáltat a k övetkező képlet: x = a ϕ ( m )−1b Prímfelbontás, prímtesztek A számok prímtényezős felbontása általános iskolai anyag, ezért egyszerű feladatnak tűnik. Bizonyos szempontból az is, mert jól definiált, könnyen

tanulható-tanítható algoritmusa van, viszont azt kell mondanunk, hogy gyakorlati kivitelezhetőség szempontjából (nagy számokra) az egyik legnehezebb feladat, ugyanis az általános iskolában tanult módszernél fejlettebb nem is nagyon van. Lényegében – szerencsétlen esetben – a szám négyzetgyökéig végig kell próbálgatni a prímekkel való oszthatóságot egyenként, esetleg bizonyos egyszerű eseteket (pl 2vel, 3-mal osztható számokat) kihagyva Gyakorlatilag az egész szalmakazlat át kell bogarászni a tűért, ha a számnak nagy prímosztói vannak Ezt a munkát persze lehet számítógépesíteni, ami pár nagyságrendet növel a sebességen, de nem nehéz olyan nagy számok közé keveredni, ahol ez sem segít Például ha valaki vesz két darab százjegyű prímet, és az összeszorzásukkal kapott (200 jegyű) számot nyilvánosságra hozza, abból a prímtényezők a ma létező matematikai módszerekkel a jövőben elméletileg elképzelhető

legnagyobb számítási kapacitással sem fejthetők meg 4 milliárd éven belül. Ez jelenleg egy olyan bombabiztos titoknak tűnik, amire megfelelelő módszerekkel biztonságos titkosító kódolások alapozhatók. Erre a titokra épít az RSA-módszer, a nyilvános kulcsú titkosírások egyik legelterjedtebb képviselője. No de hogyan fogunk nagy prímeket találni? Végülis a középfokú matematikában a „prímség” eldöntése is a prímfelbontás-módszerhez kötött: keressük a szám prímosztóit, és ha nem találunk, az jelenti azt, hogy prímet találtunk. Léteznek azonban közvetlen módszerek is annak eldöntésére, hogy egy szám prím-e, melyek közvetlenül, a prímfelbontás felhasználása nélkül működnek: ezek az ún. prímtesztek A prímtesztek alapja éppen a fentebb említett Fermat-tétel Ebben ugyan a következtetési irány csak abban az irányban garantált, hogy prím esetén a kongruencia teljesül, mert visszafelé nem okvetlenül igaz.

Tehát prímekre biztosan teljesül a tétel állítása, összetettekről nem mond semmit, tehát nem megfordítható. Viszont a vizsgálatok azt mutatják, hogy ennek nem sok híja van, a következtetés majdnem kétirányú, ugyanis összetettekre – néhány ritka kivételtől eltekintve – a tétel állítása nem igaz. Így egy tetszőleges p-re a Fermat-tételben szereplő egyszerű összefüggés egyetlen a-ra való teljesülése is majdnem biztosan garantálja, hogy prímet találtunk. Vannak számok, amik annak ellenére, hogy nem prímek, mégis átcsúsznak a teszten, ezek az ún álprímek Ezek nagyon ritkák a prímekhez képest, az álprímek listájának eleje a következő: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 1 15921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657,

825265, 838 201, 852841, 997633, 1 024651, 1033669, 1050985, 1082809, Ezek tehát azon ritka összetett számok, melyekre annak ellenére teljesül a Fermat-tétel (valamilyen a-ra), hogy az többnyire csak prímekre szokott. Ezek igen ritkák; pl a fenti lista utolsó tagjáig a p rímek száma 84483, a l ista 47 elemet tartalmaz, ez azt jelenti, hogy kb. minden 1800. prím álprím, és a nagyobb számok között ez tovább ritkul Ráadásul egy kicsit finomított módszerrel ezek jó része kiszűrhető Például a fenti lista közül sokról ránézésre kiabál, hogy osztható 5-tel vagy 3-mal. Vannak olyanok álprímek is, melyek bizonyos a értékek mellett átcsúsznak, mások viszont már lebuktatják. Így tehát a módszerek finomításával, esetleg többszörös rostával, speciális kiegészítő tesztekkel még az álprímek java is lebuktatható. Léteznek aztán olyan álprímek, melyeket minden rostán átcsúsznak, ezek az ún. univerzális álprímek. Ezek azonban

már valóban annyira ritkák, hogy gyakorlatilag majdnem 100%-ig bízhatunk egy jó prímtesztben. Nem szép persze, hogy elméletileg nem 100% a biztonság, de egyelőre ez van. Hatványozás modulussal Többek között a prímtesztként használatos Fermat-tételben, vagy a fent látott lineáris kongruencia megoldásánál, vagy az RSA-kódolás alkalmazásánál is felmerül az a feladat, hogy hatványt kell képezni adott modulus mellett: a k mod m = ? Esetenként az ebben szereplő számok mindegyike elég nagy tud lenni, ami igen nehézkes, esetleg gyakorlatilag elvégezhetetlen számolást eredményezhetne, ha direkt akarnánk elvégezni a hatványozást, majd az eredmény maradékos osztását. Ha viszont már a hatványozási folyamat közben a keletkező túl nagy számokat mindig velük kongruens kisebbekkel helyettesítjük, akkor a feladat megoldható. Például. 3589 mod1000 = ? Ez a szám bőven a legtöbb zsebszámológép kapacitása fölött van (több mint 100

jegyű), legalábbis pontosan kijelezni nem képes, esetleg normálalakban, sok értékes jegy elvesztésével. Mégis válaszolni tudunk a kérdésre a következők szerint: ( ) 8 Bontsuk szét a feladatot: 3589 = 358⋅10+9 = 3510 ⋅ 359 Számítsuk ki az egyes tényezőket az adott modulussal, kezdjük az egyszerűbbel. (A kongruenciák modulusa mindig 1000, nem írjuk ki mindenhol külön) ( ) 3 359 még túl nagy, ezért ezt felírjuk 353 alakban. 353 = 42875 ≡ 875 , ezt helyettesítve (35 ) 3 3 ≡ 8753 = 669921875 ≡ 875 . Tehát 359 ≡ 875 ( ) 2 3510 pl. 355 alakban is tárgyalható lenne, de előző felhasználásával még egyszerűbb: 3510 = 359+1 = 359 ⋅ 35 ≡ 875 ⋅ 35 = 30625 ≡ 625 ( Ebből 3510 ) 8 ( ) 4 ≡ 6258 = 625 2 ( = 3906254 ≡ 625 4 = 625 2 ) 2 ≡ 625 2 ≡ 625 . Tehát 3580 ≡ 625 . ( ) 8 Végül 3589 = 358⋅10+9 = 3510 ⋅ 359 ≡ 875 ⋅ 625 = 546875 ≡ 875 , tehát 3589 ≡ 875 mod1000 . Egy ilyesfajta,

vagy ennél jobb algoritmus gépesítésével igen nagy számokra is pillanatok alatt számítható az eredmény. Ez azt jelenti, hogy miközben egy elég nagy, kis prímosztókkal nem rendelkező szám szorzattá bontása gyakorlatilag lehetetlen, a prímségre adandó eldöntendő kérdés prímtesztekkel pillanatok alatt megválaszolható. Ha figyelembe vesszük, hogy a prímszámtételnél látottak szerint még a 100 jegyű számok között is majdnem minden 200. prím, akkor világos, hogy pár tucat, esetleg pár száz véletlenszerűen választott szám tesztelésével bárki találhat magának két nagy prímszámot, melyek szorzata mások számára gyakorlatilag felbonthatatlan. Ráadásul mindenkinek „jut” szinte biztosan különböző, amit felhasználhat az RSA-sémában