UCLA Mersenne Prime

Oriģināls raksts: https://www.math.ucla.edu/~edson/prime/

2008 gada augustā vienā no datoriem, kas pieder UCLA Matemātikas departamenta Programmai skaitļošanā (PIC), tika atklāts jauns Mersenne Prime numurs . Izrādās, ka šis skaitlis ir pasaulē lielākais zināmais pirmskaitlis, un atklājums ir izraisījis lielu interesi. Cenšoties ietaupīt ikviena laiku un enerģiju, es domāju, ka ievietošu informāciju tīmeklī FAQ formātā.

Tā kā vairāki mani saņemtie jautājumi ir nākuši no cilvēkiem ar netehnisku izglītību (tostarp bērniem), šis FAQ nav tehnisks. Tomēr jums ir jāzina, kas ir galvenais skaitlis.

Tomēr esmu spiests piedāvāt šo brīdinājumu: lai gan es strādāju matemātikas nodaļā, es esmu sistēmas administrators, nevis matemātiķis! Ja meklējat nopietnu Mersenne Prime informāciju, es aicinu jūs uz Krisa Kaldvela lielisko vietni Mersenne Primes: History, Theorems and Lists. Citas interesantas vietnes ietver Volframa Mersennas premjera lapu un Lendona Kērta Nolla izklaidējošo Mersenne Prime Digits and Names.

Tagad pie jautājumiem!

J. Kas tad ir Mersenne Prime?

A. Īsumā, pastāv noteikta pirmskaitļu apakšklase, kas pazīstama kā Mersenne Primes . Tie ir nosaukti 17. gadsimta matemātiķa Merina Mersenna vārdā. Šīs rakstīšanas laikā ir zināmi mazāk nekā 50 Mersenne Primes.

Visi Mersena pirmskaitļi ir 2 P -1 formā , kur P ir zināms pirmskaitlis. Pirmais Mersena pirmskaitlis ir 3, jo 2 2 -1 = 3. Ņemiet vērā, ka eksponents P ir pirmskaitlis, šajā gadījumā 2. Nākamais Mersena pirmskaitlis ir 7, jo 2 3 - 1 = 7, un P ir pirmskaitlis 3. . Tālāk seko 31 (2 5 — 1), pēc tam 127 (2 7–1 ), 8191 (2 13)- 1) un 131071 (2 17 - 1).

Kā redzat, pēc dažiem pirmajiem Mersenne Primes kļūst liels ļoti ātri. Šeit ir jauka zināmo Mersenne Primes tabula, kas dos kādu perspektīvu.

Mazākie no šiem skaitļiem bija zināmi senatnē, bet vēl 1951. gadā tika atklāti tikai 12. Pēdējo 50 gadu laikā ar datoru palīdzību ir atklāti vēl vairāki desmiti. Jaunākie atklātie Mersenne Primes ir satriecoši lieli, ar miljoniem ciparu. UCLA Mersenne Prime ir aptuveni 12,9 miljonus ciparu garš.

Ņemiet vērā, ka visi Mersena pirmskaitļi ir pirmskaitļi, bet ļoti maz pirmskaitļu ir Mersena pirmskaitļi.

J. Kas ir UCLA Mersenne Prime? Kāpēc tas ir īpašs?

A.UCLA Mersenne Prime ir pirmais atklātais pirmskaitlis, kurā ir vairāk nekā 10 miljoni ciparu. Tas tika atklāts UCLA matemātikas nodaļā 2008. gada 23. augustā.

Visas Mersenne Primes ir īpašas, jo tās ir tik reti sastopamas, taču šim ir pievērsta īpaša uzmanība, jo tā kvalificējas balvai (skatīt zemāk).

UCLA Mersenne Prime numurs ir 2 43112609 — 1. Faktiskais skaitlis sastāv no 12 978 189 cipariem. Ja jums ir tik vēlme, ilggadējais Mersenne Prime pētnieks Lendons Kērts Nolls ir padarījis pašu numuru pieejamu šeit . Ja jūs patiešām vēlaties, viņš šeitsniedz arī visu numuru angļu valodā (visi 328 megabaiti).

J. Vai šī ir UCLA pirmā Mersenne Prime?

A. Patiesībā šis ir astotais UCLA Mersenne Prime!

1952. gadā profesors Rafaels Robinsons atrada 5 jaunus Mersenne Primes, izmantojot UCLA Standards Western Automatic Computer (SWAC), kas ir viens no tā laika ātrākajiem datoriem. Tie bija no 13. līdz 17. atklātajiem Mersenne Primes, un katrā no tiem bija simtiem ciparu. Robinsona Mersenne Primes bija pirmie, kas tika atrasti 75 gadu laikā, un pirmie, kas tika atklāti, izmantojot digitālo datoru.

1961. gadā UCLA matemātiķis Aleksandrs Hurvics atklāja 19. un 20. Mersenne Primes uz UCLA datoru centra IBM 7090 lieldatora. Katrā no šiem cipariem bija vairāk nekā 1200 cipari.

Tagad, 47 gadus vēlāk, UCLA tradīcija atrast Mersenne Primes turpinās!

J. Kas meklē Mersenne Primes? Kā viņiem iet?

A. Tūkstošiem cilvēku, kas izmanto desmitiem tūkstošu datoru, piedalās Great Internet Mersenne Prime Search (GIMPS), organizētā darbā, kas veltīts Mersenne Primes meklēšanai. Šis ir viens no daudzajiem centieniem izplatītās skaitļošanas jomā un, iespējams, visveiksmīgākais.

Meklēšana ir ļoti labi organizēta. Primenet labie ļaudis ir koordinējuši centienus pēdējos 12 gadus un nodrošina lielisko Prime95 .programma bez maksas ikvienam, kas vēlas to palaist. Viņi seko, kuri numuri ir pārbaudīti, un nodrošina nepārtrauktu nepārbaudītu kandidātu numuru plūsmu GIMPS kopienai. GIMPS dalībnieki tiek sarindoti pēc viņu produktivitātes. Jūs varat mūs atrast ar nosaukumu UCLA_Math; mēs parasti atrodamies kaut kur starp 40. un 55. vietu.

Var paiet vairāki mēneši, lai pārbaudītu tikai vienu kandidātu numuru, taču, izmantojot internetam pieslēgtu atsevišķu datoru jaudu visā pasaulē, var panākt strauju progresu.

J. Kādas ir izredzes atklāt Mersenne Prime?

A. Saskaņā ar GIMPS projektu, izredzes, ka jebkurš kandidāts izrādīsies Mersenne Prime, ir 1 pret 150 000.

J. Kā jūs faktiski pārbaudāt numurus, lai noskaidrotu, vai tie ir Mersenne Primes?

A. Ir daudz skaitļu formā 2 P - 1, bet tikai daži no tiem ir Mersenne Primes. Ir vairāki paņēmieni, lai pārbaudītu šos skaitļus, lai noskaidrotu, vai tie ir Mersena pirmskaitļi, taču sākotnējā metode ir mēģināt faktorēt kandidāta eksponentu P un pēc tam mēģināt faktorēt kandidāta pirmskaitli 2 P -1 , izmantojot daži mazi pirmskaitļi.

Ir 75 gadus vecs algoritms, ko sauc par Lucas-Lehmer testu , kas ir plaši atzīts par labāko Mersenne Primes testēšanas rīku. Programma Prime95 plaši izmanto šo metodi, kā arī dažas citas. Paskaidrojums ir ārpus šī dokumenta darbības jomas, taču ieinteresētais lasītājs var uzzināt vairāk šeit.

J. Labi, kāpēc cilvēki meklē Mersenne Primes? Kam tie ir piemēroti?

A. To pašu iemeslu dēļ, kādēļ cilvēki kāpj kalnos, kuģo nezināmās jūrās un pēta kosmosu. Tas ir izaicinājums! Ir aizraujoši virzīt skaitļošanas matemātikas aploksni un meklēt kaut ko nezināmu, kas, jūsuprāt, ir tur. Kā bonuss, atšķirībā no seno laiku pētniekiem, mēs varam sēdēt ērtos biroja krēslos, kamēr mēs meklējam!

Tas nenozīmē, ka Mersenne Primes nav matemātiskas vērtības. Tie noteikti ir vērtīgi kriptogrāfijas jomā, un tiem var būt citi lietojumi, kas vēl nav atklāti.

Pirmskaitļu pētnieks Kriss Koldvels šo jautājumu padziļināti izpēta savā rakstā "Kāpēc cilvēki atrod šos pirmskaitļus?".

J. Papildus izaicinājumam, kāpēc jūs nolēmāt piedalīties?

A. Tāpat kā daudzās citās vietnēs, mēs sapratām, ka mūsu lielā (75 sēdvietas) PIC/Math Computer Lab izmanto tikai nelielu daļu no pieejamās CPU jaudas. Tā vietā, lai ļautu visiem šiem cikliem iet velti, mēs apskatījām vairākus izplatītus skaitļošanas projektus, nosakot , ka GIMPS mums ir vispiemērotākais. Papildus tam, ka GIMPS ir matemātikas projekts, mēs atklājām, ka tas bija ļoti labi uzrakstīts un netraucēja datoru lietotājiem bakalaura programmās (tas neattiecās uz kādu citu mūsu pētīto projektu programmatūru).

Programma datorikā (PIC)piesaista studentus no galvenajām iestādēm visā universitātes pilsētiņā, tāpēc mums bija svarīgi, lai visi laboratorijas mēroga skaitļošanas projekti būtu saprotami visiem iesaistītajiem. GIMPS noteikti atbilst šim mērķim, un kā bonusu mēs domājām, ka neformālajai sacensībai starp GIMPS vietnēm būtu interesanti sekot mūsu studentiem, un tas palielinātu viņu izpratni par skaitļošanas matemātiku.

J. Ko jūs darījāt, lai to palaistu? Vai tas bija sarežģīti?

A. Programmatūra GIMPS Prime95 ir ļoti vienkārša no sistēmas administratīvā viedokļa. To ir viegli uzstādīt, un tai nav nepieciešama apkope.

Programmatūra Prime95 izsniedz regulārus atjauninājumus par tās apstrādes statusu centrālajiem Primemenet datoriem. Ja iekārta, kurā tā darbojas, palēninās, aprēķini tiks atsākti no vietas, kur tie tika pārtraukti, kad dators atgriežas. Ja atsevišķa kaste ilgstoši nedarbojas, Primenet atgūs numuru un piešķirs to kādam citam, kā arī piešķirs jaunu numuru, kad iekārta atgriezīsies ekspluatācijā.

J. Kā darbojas verifikācija?

A. Kad Mersenne Prime tiek atrasts, oficiāls paziņojums netiek sniegts, kamēr neatkarīga trešā puse nav apstiprinājusi prasību. Ar īpaši lieliem skaitļiem, piemēram, šiem, vienmēr pastāv neliela skaitļošanas problēma ar izmantoto algoritmu vai pašu datora centrālo procesoru (Intel peldošā komata problēmair klasisks piemērs tam).

Šo iespējamo problēmu dēļ Mersenne Primes vienmēr tiek apstiprināti, izmantojot pilnīgi citu algoritmu datorā ar atšķirīgu arhitektūru. Verifikācija var ilgt divas nedēļas vai ilgāk.

J. Kad notika atklājums? Kāds dators tika izmantots?

A. Par UCLA Mersenne Prime tika ziņots 2008. gada 23. augustā datorā ar nosaukumu zeppelin.pic.ucla.edu — Dell Optiplex 745, kurā darbojas sistēma Windows XP ar Intel Core 2 Duo E6600 centrālo procesoru, kas darbojas 2,4 GHz. Nosaukums "cepelīns" bija daļa no mūsu Classic Rock Band datoru sērijas.

J. Kas tas viss par naudas balvām?

A. Electronic Frontier Foundation(EFF), interneta pirmizrādes pilsonisko brīvību organizācija, sponsorē Cooperative Computing Awards. Šīs balvas ir paredzētas, lai "iedrošinātu parastos interneta lietotājus sniegt ieguldījumu milzīgu zinātnisku problēmu risināšanā", un tām tiek piešķirtas naudas balvas, kad tiek sasniegti noteikti kritēriji.

EZF ir piešķīrusi pastāvīgu balvu USD 100 000 apmērā par pirmo pirmskaitļu ar 10 miljoniem ciparu, kas jāatklāj. UCLA Mersenne Prime ir gandrīz 12,9 miljoni ciparu, un tas atbilst piešķiršanas kritērijiem. Tiklīdz oficiālie rezultāti tiks publicēti atbilstošā žurnālā, balva tiks piešķirta. Tas būs agrākais 2009. gadā.

Pēc iepriekšējas vienošanās, tikai 50% no balvas saņems 10 miljonu ciparu pirmskaitļa atklājējs. 25% ir paredzēti labdarībai, un, atzīstot GIMPS sadarbības raksturu, lielāko daļu atlikušo 25% saņems citu Mersenne Primes atklājēji, bet neliela summa tiks piešķirta pašam GIMPS.

J. Ko es dzirdu par plakātu? Vai tāds būs UCLA Mersenne Prime?

A. Jau gadiem ilgi uzņēmums ar nosaukumu Perfectly Scientific ir veidojis plakātu ar lielāko pašlaik zināmo izteikto pirmskaitļu. M44 plakātā, kas tika ražots 2006. gadā, tika izmantots ārkārtīgi mazs fonts, lai uz viena 29 x 40 collu plakāta izspiestu 9,8 miljonus ciparu. Uzņēmums kopā ar plakātu piedāvāja juveliera lupatu, lai to varētu izlasīt.

Richard Crandall no Perfectly Scientific nesen sazinājās ar mani, lai paziņotu, ka UCLA Mersenne Prime plakāts tagad ir pieejams iegādei. Tas maksā 99 ASV dolārus bez rāmja un ir pieejams Perfectly Scientific tīmekļa vietnē.

J. Kā ir ar otru nesen atklāto Mersenne Prime?

A. Divas nedēļas pēc UCLA Mersenne Prime atklāšanas Hans-Michael Elvenich Vācijā atklāja vēl 10 miljonus ciparu plus Mersenne Prime. Ar 11,2 miljoniem ciparu tas ir par aptuveni 10% mazāks nekā UCLA Mersenne Prime.

Šī nav pirmā reize, kad Mersenne Primes tiek atklāts no ierindas. 1988. gadā Colquitt un Welsh atklāja Mersenne Prime, kas ir mazāks par iepriekšējiem diviem, atklātiem 1983. un 1985. gadā.

Šīs rakstīšanas laikā UCLA Mersenne Prime tika uzskatīts par 46. Mersenne Prime (Mersene Prime meklētāju kopiena to sauca par "M46", lai gan tas bija 45. atklātais). Elvenich Mersenne Prime ir M45, bet tika atklāts 46.!

Vēl viens sarežģījums ir tas, ka nav pārbaudīti visi potenciālie pirmskaitļi starp M39 (atklāts 2001. gadā) un UCLA Mersenne Prime, tāpēc nākotnē šajā diapazonā varētu atrast vairāk. Ja tā ir, UCLA Prime tiks "paaugstināts" uz M47.