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