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