Tartalomjegyzék
A napló közvetlen linkje:
http://teveclub.hu/naplo/232609
|
2008-05-08
M.2.6. Mersenne-prímek
Ezek a sajátos prímszámok nem csak önmagukban érdekesek. Távirati stílusban egy kapcsolódó terület: a tökéletes számok kérdésköre. (Tökéletes az a szám, mely egyenlõ nála kisebb osztóinak összegével, mint például a 6, a 28). A Mersenne-prímek segítségével könnyen lehet páros tökéletes számot csinálni: ugyanis már Euklidesz bebizonyította (némileg más alakban), ha p és q prímek, ahol
q=2^p-1
akkor az
n=2^(p-1)*q
szám tökéletes lesz, sõt Eulernek egy, halála után elõkerült dolgozatából tudjuk, hogy csak ezek a számok lehetnek "párosan" tökéletesek. Eddig 30 darab páros tökéletes szám ismeretes, de a mai napig eldöntetlen, hogy vannak-e páratlan tökéletes számok (mindenesetre
100^200
-ig nem sikerült ilyet találni).
Van egy másik – gyakorlati szempontból fontosabbnak tûnõ – terület, ahol a Mersenne-prímek szintén komoly szerephez jutnak. Ez pedig a kriptográfia; a titkosírás, rejtjelezés tudománya. Az 1978-ban publikált RSA-módszer (a név a fejlesztõk, a MIT munkatársai nevébõl adódik: Rivest-Shamir-Adleman) a kis Fermat-tétel egy következményét használja. Nagyon leegyszerûsítve egy olyan eljárásról van szó, melynél a kódolás elve nem titkos, sõt az üzenet is nyilvános csatornákon közölhetõ, ennek ellenére a megfejtés reménytelen. Mind a kódoláshoz, mind a dekódoláshoz sokjegyû, nagy prímek kellenek (mondjuk 100 jegyûek), s a kívülrõl való megfejthetetlenség is azon alapszik, hogy a mai körülmények között többszáz jegyû számok prímfelbontása elvégezhetetlen reális, értelmes idõn belül. (A módszer matematikai háttere, mûködése kiválóan megérthetõ dr. Szalay Mihály: Számelmélet címû, Tankönyvkiadónál megjelent, a matematikai osztályok számára készült könyvébõl). Mersenne módszere pedig igencsak alkalmas nagy prímek gyors elõállítására.
Zárásul egy adalék, mely valahol utal a számítástechnika rohamos fejlõdésére is: a feladat kitûzésének apropóját egy 1991 novemberi közlemény adta, egy 227832 jegyû rekord-prím megtalálásáról. Nos, azóta a New Scientist hírt adott egy újabb csúcsról (ez is Mersenne-prím), melynek értéke
2^859433-1
jegyeinek száma pedig 258716. Megtalálói Gage és Slowinski, a Cray Research Inc. munkatársai. Míg az elõzõ világcsúcs megkeresése 19 óráig tartott, addig az újabb (csekély 30 ezer jeggyel hosszabb) szám fél óra alatt megkerült, egy Cray Y-MP szupergépen.
2006. szeptember 4-én fedezték fel a 44-edik Mersenne-prímet, ez a
2^32 582 657−1
szám, amely 9 808 358 számjegyű. Ez egyben a jelenleg ismert legnagyobb prímszám és ez a GIMPS projekt tizedik prímrekordja.
|
