fizikusok - matematikusok oldala
Névjegy

Fizikát kedvelők oldala

 

 
Matematika
 
Fizika
 
Geometria
 
Algebra
 
Kinematika
 
Programozás
 
Pedagógia
 
Zrinyi Ilona Gimnázium
 
Minisztériumok
 
Magyar Tudományos Akadémia
 
OFOE
 
Rényi Alfréd Matematikai Kutató Intézet
 
Állami Eötvös Lóránd Geofizikai Intézet
 
KFKI
 
Fizikai kisérletek
 
Miskolc Önkormányzata
 
TÁKISZ
 
Menetrend
 
Bejelentkezés
Felhasználónév:

Jelszó:
SúgóSúgó
Regisztráció
Elfelejtettem a jelszót
 
Óra
 
Hírek
Hírek : Az ókori számmisztika határozott igen-nel válaszolt erre a ...

Az ókori számmisztika határozott igen-nel válaszolt erre a ...

  2004.12.04. 15:24

Dénes Tamás

Piérre Fermat

és a nyilvános kulcsú rejtjelzés

 

Szinte hónapra pontosan  100 évvel Girolamo Cardano születése után, 1601-ben született meg  Piérre Fermat. Bár Fermat, Cardanohoz hasonlóan sokoldalú tudós volt, aki nemcsak korának, hanem az egész tudománynak (nem csak a matematikának) jelentõs alakja, mégis nevéhez többnyire csupán a "Fermat sejtés" tapad. Valószínûleg ez a sejtéshez fûzõdõ különös történetnek köszönhetõ, amely szerint Fermatról ránk maradt Diophantosz "Aritmetikájának" egy 1621-ben kiadott példánya, amelyben számos megjegyzést irt a könyv különbözõ helyeire. E megjegyzések a Diophantosz által felvázolt problémákkal kapcsolatosak és igen sok értékes anyagot szolgáltatnak a matematikusoknak, fõleg a számelmélet területérõl. Az egyik ilyen megjegyzésben, melyet  egy lap margójára irt, Fermat arra utal, hogy az    egyenletnek nincsenek  természetes számokra zérustól különbözõ egész megoldásai. A könyv margóján ez olvasható: "Ennek igazán bámulatos bizonyítását találtam meg, azonban a könyv margója túlságosan keskeny, hogy ide írjam."

 

Ettõl kezdve a matematikusok és érdeklõdõ nem matematikusok állandóan igyekeztek a bizonyítást megtalálni, vagy egy olyan példát keresni, amely megdönti Fermat állítását.

A kételkedõk szerint Fermat nem is bizonyította be ezt a tételt, ezért az  1990-es évek közepéig, amíg a bizonyítást valóban sikerült megadni, Fermat sejtésnek nevezték. A kételkedõk érveit nagyban alátámasztotta, hogy Fermatnál elég gyakran fordulnak elõ téves matematikai állítások, ilyen például, hogy "minden  alakú szám prím, ha  n  természetes szám", ezeket nevezzük Fermat számoknak.

A Fermat sejtés bizonyítási kísérleteire lelkesitõleg hatott, hogy  1908-ban  Wolfskehl német matematikus  100 ezer márkát adott át a Göttingai Tudományos Társaságnak, hogy jutalomként fizesse ki annak, aki a sejtés bizonyítását megtalálja, vagy téves voltát bebizonyítja. Több mint  300 éves szunnyadás után a XX. században több részleges eredményt sikerült elérni elég nagy, de mégis véges  n  értékekre, míg Andrew Wiles amerikai matematikus  1993-ban bejelentette a szenzációt, hogy sikerült a teljes bizonyítást megtalálnia. Nemsokára kiderült, hogy Wiles bizonyítása hiányos. Ezt azonban  Richard Taylorral közösen sikerült pótolni 1994-ben, így  1995-ben az  Annals of Mathematics  141. számában a teljes bizonyítás megjelenhetett. Magyar nyelven is tájékozódhat a kedves Olvasó  Rónyai Lajos dolgozatából  (Matematikai Lapok, új sorozat 2., 3-4. szám).

Így  1995-óta jogosan beszélhetünk sejtés helyett nagy Fermat tételrõl. A  "nagy" jelzõ a "kis" Fermat tételtõl való megkülönböztetésre szolgál, amelyrõl a következõkben lesz szó és amelynek "kis" jelzõje ellenére alapvetõ hatása van napjaink információ titkosítására. Fermat eredetileg a következõ tételt mondta ki:

Kis Fermat tétel:

Ha  p  prímszám és  a  nem osztható  p-vel, akkor teljesül az (1) kongruencia[1]

 

(1)                                            

 

Fermat bizonyítása azonban ebben az esetben sem maradt fenn. Az elsõ bizonyítás majd 100 évig váratott magára és  Leonhard Eulertõl  (1707-1783) a XVIII. század matematikus óriásától származik. Euler egyben a tétel általánosítását is bebizonyította, így ma  Euler-Fermat tételnek nevezzük, amely így szól:

Euler-Fermat tétel:

Ha    egész szám és  (a,m)=1, azaz  a  és  m  relatív prímek[2], akkor

 

(2)                                     

 

 

Hogy ez valóban a kis Fermat tétel általánosítása, ahhoz a    Euler-féle függvény értelmezésérõl kell beszélnünk.    jelenti a  0, 1, 2, ..., m-1  számok közül az  m-hez relatív prímek számát.

Például: 

 

Általában igaz a tétel, hogy ha  m=p  prímszám, akkor

 

(3)                                           

 

Ebbõl az is könnyen belátható, hogy ha  p  és  q  különbözõ prímek, akkor

 

(4)                                  

 

 

 

A prímszámoknak és a számok osztóinak titokzatos szerepet tulajdonítottak az ókori számmisztikában olyannyira, hogy Püthagorasz és követõi, akik e számmisztika fõ hirdetõi voltak (i.e. VI-V. század), úgy tartották, hogy "A dolgok természete, lényege: a szám."  De nem csak hirdették, hanem valóban a természeti és társadalmi jelenségeket mind-mind a számok csodálatos tulajdonságai "testesítették meg". A pütagoreusok ugyanis nem a számokat személyesítették meg, hanem a személyes (emberi) tulajdonságokat "számosították meg".

 

Tökéletesnek tartottak egy számot, ha az megegyezett osztói összegével. Tökéletes számok[3] például a  6=1+2+3  és a   28=1+2+4+7+14 . A pütagoreusok csak néhány tökéletes számot ismertek, így a 496-ról és a 8128-ról is tudták, hogy tökéletes számok. A matematikusok az ókor óta nem tudják, hogy van-e végtelen sok tökéletes szám.

Az ötödik tökéletes számot, a 33.550.336-ot a XV. században találták meg, míg a XVI. század adta a hatodik és hetedik tökéletes számot, a  és a . Látható, hogy a tökéletes számok között, ahogy haladunk "elõre" egyre nagyobb távolságok vannak, így nem meglepõ, hogy egyre nehezebb újabb tökéletes számokat találni. A nyolcadik tökéletes szám megtalálására a XVIII. századig kellett várni, amikor Leonhard Euler kimutatta, hogy a  is tökéletes szám. A számítógépek megjelenéséig még négy tökéletes számot sikerült megtalálni a XIX. században kézi számolással, ezek a , , ,   tökéletes számok[4].

Modern számítógépekkel a XX. században már egyre nagyobb tökéletes számokat sikerült elõállítani, például ma már tudjuk, hogy  , , , , , , ,  is tökéletes számok[5].

De a pütagoreusok szerint vannak barátságos számok is. Két szám akkor áll barátságban egymással, ha az egyik osztóinak összege pontosan a másik számot adja és fordítva. Barátságos számok például a  220 és  284, ugyanis

 

220  osztói:          1+2+4+5+10+11+20+22+44+55+110=284

 

284 osztói:           1+2+4+71+142=220

 

A barátságos számok felfedezésének története is sok évszázados történet. Már a régiek ismerték az 1184 és 1210 barátságos számpárt, majd Piérre Fermat mutatta ki ugyanezt a 17296 és 18416 számpárról. René Descartes (1596-1650), aki szintén a matematika egyik óriása volt[6] fedezte fel a  9363584 és 9437056 barátságos számpárt, majd Euler a XVIII. században még  61 barátságos számpárt határozott meg.

 

 

 

A számmisztika már régen homályba merült, de a harmóniába, a harmonikus szépségbe vetett hit napjainkig fennmaradt. De fennmaradt az a számtalan örökérvényû gondolat, tudományos tétel is, amely e misztikus gondolkodás talaján fogant és mégis a természet mély összefüggéseit írja le. Mint a bemutatott példák is mutatják, néha olyan mély titkokat sikerült a pütagoreusoknak "számszerûsíteni", hogy még a mai napig sem tudta az emberiség a megfejtést megtalálni.  Napjaink kriptográfiája[7] nagy részben ezekre az évezredes meg nem fejtett titkokra épül.

 

Igen érdekes magyar vonatkozásokra derül fény a prímszámokkal és a kis Fermat tétellel kapcsolatban, Kiss Elemér marosvásárhelyi matematikus és Bolyai kutató tollából. 1999-ben megjelent könyvében (lásd [8]) egészen új képet kapunk Bolyai Jánosról, eddig ismeretlen dokumentumokra alapozva. Kiss Elemér könyvébõl kiderül, hogy Bolyai János leginkább a prímszámokkal szeretett foglalkozni, errõl így ír Õ maga:

"Az egész számtan sõt az egész tan mezején alig van szebb és érdekesebb ... s a legnagyobb nyiászok (matematikusok) figyelme és eleje óta elfoglalt tárgy, mint a fõszámok (prímszámok) oly mély homályban rejlõ titka."[8]

Bolyai is, mint a Pütagoreusok óta annyi matematikus, kereste az úgynevezett prímszám képletet, vagyis olyan formulát, amely közvetlen összefüggést ad meg az  n-edik prímszám értéke és az  n  index között. 1855 tájékán még úgy gondolta, hogy sikerült megtalálnia a titok megfejtését:

"Azt megmutatni, hogy bármely    alakú szám prím mihelyt  p  prím, ugyanakkor amikor a  -gyel bajlódám, magam is megkísértettem, mert amint irataim is megmutatják én is abban a sejtelemben voltam, hogy    mindig prím, ha  p  prím. Ez egy történeti fontosságú felfedezése volna a legelsõ olyan függvénynek, mely mindig prímet ad. Azonban ez sem valósul meg, mert például   ..."[9]

 

Apja (Bolyai Farkas) ösztönzésére megkísérelte a kis Fermat tétel fordítottját bebizonyítani, mivel ha ez sikerül, akkor megkapta volna a vágyott prímszámképletet. A kis Fermat tétel fordítottja azt mondja ki, hogy ha   osztható  p-vel, akkor  p  biztosan prímszám. Néhány kísérlet után azonban rádöbbent, hogy a bizonyítás lehetetlen, mivel a kis Fermat tétel fordítottja általában nem érvényes. Ellenpéldákat keresve, felfedezte a legkisebb úgynevezett pszeudoprím számot, a  341-et.

 

Vannak ugyanis olyan  n  összetett számok, amelyek minden  n-hez relatív prím  a-ra kielégítik a kis Fermat tételt, vagyis

 

(5)                              ahol   n  összetett szám és  (a,n)=1

 

Az ilyen  n  számokat nevezzük  Carmichael számoknak, melyekrõl csak a XX. század közepén sikerült bebizonyítani, hogy végtelen sok létezik belõlük.

Az olyan összetett  n  számokat, amelyekre az  (5)  összefüggés  a=2 esetén teljesül, 2-re vonatkozó pszeudoprímeknek, vagy álprímeknek nevezzük.

 

Az álprímek történetében Bolyai János fontos szerepet játszott, amely Kiss Elemér kutatásai nélkül mindmáig ismeretlen maradt volna.

 

A modern kriptográfia az  1970-es években újra "felfedezte" a számelméleti eszközök felhasználásának elõnyeit. Az idõpont talán nem véletlen, hiszen ekkorra tehetõ a globális információs rendszerek, a globális kommunikáció, az "információ robbanás" korszakának kezdete, amely óriási kihívást jelentett az információk biztonságos tárolásával és továbbításával foglalkozóknak.

 

Íme a klasszikus titkosítás vázlata:

 

 


                                                           Titkos kulcs

          Nyílt üzenet[10]                                                                          Rejtjeles üzenet

                                                                           Titkosító eljárás

                     Küldõ                                                                                                                       Fogadó

 

 

 

A Fogadó fél (ha nem illetéktelen) rendelkezett ugyanazzal a titkos kulccsal és természetesen a titkosító eljárásnak megfelelõ megoldó eljárással, így a rejtjeles üzenet megoldásának (elolvasásának) vázlata:

 

 


                                                           Titkos kulcs

          Rejtjeles üzenet                                                                         Nyílt üzenet 

                                                                             Megoldó eljárás

 

 

 

A klasszikus titkosítás tehát megfelelõ (szigorú) titoktartást és pontos szervezést igényelt, hiszen a "titkos kulcs" illetéktelen kézbe kerülése, mindkét irányban végzetes lehetett. Az illetéktelen küldõ képessé vált ugyanis hamis üzenetek küldésére, amely a fogadó oldalán felismerhetetlen volt, míg az illetéktelenül a titkos kulcs birtokába jutott fogadó, képes volt a másnak címzett üzenetet elolvasni. Hétköznapi hasonlattal élve ez olyan, mintha az  egy zárral nyitható ajtó kulcsát rosszul dugjuk el és azt a betörõ megtalálja.

Ezen problémák megakadályozása érdekében a titkos kulcsot rendszeresen változtatták, ami viszont igen pontos (és titkos!) szervezést igényelt, hiszen errõl a változásról a küldõ és fogadó fél "egyszerre" kellett, hogy értesüljön.

 

 

 

W.S.Jevons már  1873-ban megjelent könyvében felvetette  (lásd  [07]) azt az elvet, hogy vannak bizonyos matematikai mûveletek, amelyek elvégzése nagyon egyszerû (ilyen például az összeadás, vagy a szorzás), de az eredménybõl a kiindulási komponensek visszaállítása igen nehéz, sokszor reménytelen. Illusztrációként bemutatja az azóta róla elnevezett  10 jegyû számot, a Jevons számot (8.616.460.799), amely két prímszám szorzata, ám a prímtényezõk meghatározását (a prímfaktorizációt) akkor reménytelennek látta[11]. Hogy Jevons ezzel a felvetésével mennyire megelõzte korát, azt mi sem bizonyítja jobban, mint hogy szinte pontosan  100 év szunnyadás után, az 1970-es évek elején merült fel ismét e gondolat. Erdõs Pál és Surányi János  [05]-ben így fogalmazza meg a problémát:

"Létezhet-e azonban olyan rejtjelzés, amelyiknél nem lehet kitalálni, hogy hogyan kell azt visszacsinálni ? Elsõ pillanatban ez valószínûtlennek látszik, mégis az Euler-Fermat tétel, továbbá a számítógépek rendkívüli teljesítõképessége egy oldalról, a teljesítõképességük határa a másik oldalról lehetõséget ad erre."

 

Az világos, hogy ahhoz, hogy az  Euler-Fermat tétel alkalmazható legyen, az üzenetnek numerikusnak kell lennie, vagyis a betûkbõl és egyéb írásjelekbõl álló szövegeket számokká kell alakítani. Ez azonban könnyen megtehetõ a klasszikus helyettesítéses titkositási eljárással, amikor mindenegyes írásjelnek egy-egy számot feleltetünk meg[12]. Napjaink digitális világában már nem csupán a szöveges üzeneteket, hanem a kép és hang üzeneteket is számok sorozatává alakítják, így tárolják és továbbítják a kommunikációs vonalakon, aminek sok más mellett pontosan az az elõnye, hogy jóval biztonságosabb adatvédelem érhetõ el, mint az úgynevezett analóg jeleknél.

Ez azt jelenti, hogy nincs akadálya annak, hogy a továbbiakban üzeneten mindig számokat értsünk. Így már kézenfekvõbbnek tûnik, hogy a számelmélet eredményeit, ezen belül az  Euler-Fermat tételt is felhasználjuk a titkosításra. Legyen eljárásunk a következõ:

 

a. Válasszunk két különbözõ  p, q  prímszámot, amelyek szorzata

 

(6)                                                  pq=N

 

b. Ha a továbbítandó üzenet (mint szám) nagyobb mint  N, akkor bontsuk fel  N-nél kisebb részekre. Egy ilyen rész legyen  h. Tehát fennáll, hogy

 

 
Miskolc
 
Ajánlott oldalak
 
Híres emberek
 
Átszámítások
 
Egyetemek
 
Gimnáziumok
 
Felvételi
 
Tételek
 
Pályázatok
 
Elektronikus Könyv kereső
 
Tanszerek
 
Tudomány és Társadalom
 
Webkamerák
 
Dák-meló
 
Időjárás
 
Térkép
 
Szerkesztőnek
 

Szeretnél egy jó receptet? Látogass el oldalamra, szeretettel várlak!    *****    Minõségi Homlokzati Hõszigetelés. Vállaljuk családi házak, lakások, nyaralók és egyéb épületek homlokzati szigetelését.    *****    Amway termék elérhetõ áron!Tudta, hogy az általános tisztítószer akár 333 felmosásra is alkalmas?Több info a weboldalon    *****    Florence Pugh magyar rajongói oldal. Ismerd meg és kövesd az angol színésznõ karrierjèt!    *****    Fele királyságomat nektek adom, hisz csak rátok vár ez a mesebirodalom! - Új menüpont a Mesetárban! Nézz be te is!    *****    DMT Trip napló, versek, történetek, absztrakt agymenés:)    *****    Elindult a Játék határok nélkül blog! Részletes információ az összes adásról, melyben a magyarok játszottak + egyéb infó    *****    Florence Pugh Hungary - Ismerd meg az Oppenheimer és a Dûne 2. sztárját.    *****    Megnyílt az F-Zero Hungary! Ismerd meg a Nintendo legdinamikusabb versenyjáték-sorozatát! Folyamatosan bõvülõ tartalom.    *****    A Cheer Danshi!! nem futott nagyot, mégis érdemes egy esélyt adni neki. Olvass róla az Anime Odyssey blogban!    *****    A 1080° Avalanche egy méltatlanul figyelmen kívül hagyott játék, pedig a Nintendo egyik remekmûve. Olvass róla!    *****    Gundel Takács Gábor egy különleges könyvet adott ki, ahol kiváló sportolókkal a sport mélységébe nyerhetünk betekintést.    *****    21 napos életmódváltás program csatlakozz hozzánk még!Január 28-ig 10% kedvezménnyel plusz ajándékkal tudod megvásárolni    *****    Szeretne egy olyan általános tisztítószert ami 333 felmosásra is elegendõ? Szeretne ha csíkmentes lenne? Részletek itt!!    *****    Új játék érkezett a Mesetárba! Elõ a papírral, ollóval, és gyertek barkácsolni!    *****    Tisztítószerek a legjobb áron! Hatékonyság felsõfoka! 333 felmosásra elengedõ általános tisztítószer! Vásároljon még ma!    *****    Hayashibara Megumi és Okui Masami rajongói oldal! Albumok, dalszövegek, és sok más. Folyamatosan frissülõ tartalom.    *****    A legfrissebb hírek a Super Mario világából és a legteljesebb adatbázis a Mario játékokról.Folyamatosan bõvülõ tartalom.    *****    333 Felmosásra elegendõ! Szeretne gazdaságosan felmosni? Szeretne kiváló általános tisztítószert? Kiváló tisztítószerek!    *****    Ha tél, akkor téli sportok! De akár videojáték formájában is játszhatjuk õket. A 1080°Snowboarding egy kiváló példa erre