De UCLA Mersenne Prime

Origineel artikel: https://www.math.ucla.edu/~edson/prime/

In augustus 2008 werd een nieuw Mersenne Priemgetal ontdekt op een van de computers van het Program in Computing (PIC) van de UCLA Mathematics Department. Dit getal blijkt het grootste bekende priemgetal ter wereld te zijn, en de ontdekking heeft veel belangstelling gewekt. In een poging om iedereen tijd en energie te besparen, dacht ik dat ik wat informatie in FAQ-formaat op internet zou zetten. Omdat een aantal vragen die ik heb ontvangen afkomstig zijn van mensen met een niet-technische achtergrond (inclusief kinderen), is deze FAQ niet-technisch. Je moet wel weten wat een priemgetal is.

Ik ben echter genoodzaakt dit voorbehoud te maken: ook al werk ik voor de afdeling Wiskunde, ik ben een systeembeheerder en geen wiskundige! Als u op zoek bent naar serieuze Mersenne Prime-informatie, verwijs ik u naar de uitstekende website van Chris Caldwell, Mersenne Primes: History, Theorems and Lists. Andere interessante sites zijn de Mersenne Prime-pagina van Wolfram en de vermakelijke Mersenne Prime Digits and Names van Landon Curt Noll.

Nu verder met de vragen!

V. Dus wat is een Mersenne Priemgetal?

A. Kort gezegd bestaat er een bepaalde subklasse van priemgetallen die bekend staat als Mersenne Priemgetallen. Ze zijn genoemd naar Marin Mersenne, een wiskundige uit de 17e eeuw. Op het moment dat dit artikel wordt geschreven, zijn er minder dan 50 bekende Mersenne-priemgetallen.

Mersenne Priemgetallen hebben allemaal de vorm van 2 P -1, waarbij P een bekend priemgetal is. Het eerste Mersenne Priemgetal is 3 omdat 2 2 -1 = 3. Merk op dat de exponent P een priemgetal is, in dit geval 2. Het volgende Mersenne Priemgetal is 7 omdat 2 3 - 1 = 7, waarbij P het priemgetal 3 is. Vervolgens komt 31 (2 5 - 1), dan 127 (2 7 - 1), 8191 (2 13- 1) en 131071 (2 17 - 1).

Zoals je kunt zien, worden Mersenne Primes na de eerste paar erg snel groot. Er is hier een mooie tabel met de bekende Mersenne Primes die enig perspectief zal geven.

De kleinste van deze aantallen waren al in de oudheid bekend, maar in 1951 waren er nog maar twaalf ontdekt. In de afgelopen vijftig jaar zijn er met behulp van computers nog tientallen meer ontdekt. De meest recent ontdekte Mersenne Priemgetallen zijn verbluffend groot, met miljoenen cijfers. De UCLA Mersenne Prime heeft een lengte van ongeveer 12,9 miljoen cijfers.

Merk op dat alle Mersenne-priemgetallen priemgetallen zijn, maar heel weinig priemgetallen zijn Mersenne-priemgetallen.

V. Wat is de UCLA Mersenne Prime? Waarom is het speciaal?

A. De UCLA Mersenne Prime is het eerste ontdekte priemgetal met meer dan 10 miljoen cijfers. Het werd op 23 augustus 2008 ontdekt op de afdeling Wiskunde van de UCLA.

Alle Mersenne Priemgetallen zijn bijzonder omdat ze zo zeldzaam zijn, maar deze heeft extra aandacht gekregen omdat hij in aanmerking komt voor een prijs (zie hieronder).

Het UCLA Mersenne Priemgetal is 243112609 - 1. Het werkelijke nummer bestaat uit 12.978.189 cijfers. Als je daartoe geneigd bent: Landon Curt Noll, een ervaren Mersenne Prime-onderzoeker, heeft het nummer zelf hier beschikbaar gesteld. Als je echt heel erg geneigd bent, geeft hij hier ook het volledige nummer in het Engels (alle 328 megabytes ervan).

V. Is dit de eerste Mersenne Prime van UCLA?

A. Eigenlijk is dit UCLA's achtste Mersenne Prime!

In 1952 vond professor Raphael Robinson vijf nieuwe Mersenne Primes met behulp van UCLA's Standards Western Automatic Computer (SWAC), een van de snelste computers van zijn tijd. Dit waren de 13e tot en met de 17e ontdekte Mersenne Priemgetallen, en elk had honderden cijfers. Robinson's Mersenne Primes waren de eerste die in 75 jaar werden gevonden, en de eerste die ontdekt werden met behulp van een digitale computer. In 1961 ontdekte

UCLA-wiskundige Alexander Hurwitz de 19e en 20e Mersenne Priemgetallen op het IBM 7090 mainframe van het UCLA Computer Center. Elk van deze nummers had meer dan 1200 cijfers.

Nu, 47 jaar later, wordt de UCLA-traditie van het vinden van Mersenne Primes voortgezet!

V. Wie is op zoek naar Mersenne Primes? Hoe gaan ze ermee om?

A. Duizenden mensen die tienduizenden computers gebruiken, nemen deel aan de Great Internet Mersenne Prime Search (GIMPS), een georganiseerde inspanning gewijd aan de zoektocht naar Mersenne Primes. Dit is een van de vele lopende inspanningen op het gebied van gedistribueerd computergebruik, en misschien wel de meest succesvolle.

De zoektocht is zeer goed georganiseerd. De goede mensen bij Primenet hebben de afgelopen twaalf jaar de inspanningen gecoördineerd en zorgen voor de uitstekende Prime95programma gratis voor iedereen die het wil uitvoeren. Ze houden bij welke nummers zijn getest en zorgen voor een gestage stroom ongeteste kandidaatnummers voor de GIMPS-gemeenschap. GIMPS-deelnemers worden gerangschikt op basis van hun productiviteit. U kunt ons vinden onder de naam UCLA_Math; we staan ​​doorgaans ergens tussen de 40e en 55e plaats.

Het kan een enkele machine maanden kosten om slechts één kandidaatnummer te testen, maar door gebruik te maken van de kracht van op het internet aangesloten individuele computers over de hele wereld kan er snel vooruitgang worden geboekt.

V. Hoe groot is de kans dat je een Mersenne Priemgetal ontdekt?

A. Volgens het GIMPS-project is de kans dat een kandidaatnummer een Mersenne Priemgetal blijkt te zijn, is 1 op 150.000.

V: Hoe test je getallen eigenlijk om te zien of het Mersenne-priemgetallen zijn?

A. Er zijn veel getallen van de vorm 2P - 1, maar slechts een paar daarvan zijn Mersenne-priemgetallen. Er zijn een aantal technieken om deze getallen te testen om te zien of het Mersenne-priemgetallen zijn, maar de eerste methode is om te proberen de kandidaat-exponent, P, te ontbinden en vervolgens het kandidaat-priemgetal, 2P -1, te ontbinden in factoren. enkele kleine priemgetallen.

Er bestaat een 75 jaar oud algoritme, de Lucas-Lehmer Test, dat algemeen wordt erkend als het beste hulpmiddel voor het testen van Mersenne Primes. Het Prime95-programma maakt uitgebreid gebruik van deze methode, evenals van enkele andere. Een uitleg valt buiten het bestek van dit document, maar de geïnteresseerde lezer kan hier meer te weten komen.

V. Oké, waarom zoeken mensen naar Mersenne Primes? Waar zijn ze goed voor?

A. Om dezelfde redenen waarom mensen bergen beklimmen, onbekende zeeën bevaren en de kosmos verkennen. Het is een uitdaging! Het is spannend om de grenzen van de computerwiskunde te verleggen en te zoeken naar iets onbekends waarvan je denkt dat het bestaat. Als bonus mogen we, in tegenstelling tot de ontdekkingsreizigers van weleer, tijdens het zoeken in comfortabele bureaustoelen zitten!

Dit wil niet zeggen dat Mersenne Primes geen wiskundige waarde hebben. Ze zijn zeker van waarde op het gebied van cryptografie en kunnen nog andere toepassingen hebben die nog ontdekt moeten worden.

Priemgetallenonderzoeker Chris Caldwell gaat dieper in op deze kwestie in zijn artikel "Waarom vinden mensen deze priemgetallen?".

V. Waarom heb je, afgezien van de uitdaging, besloten om deel te nemen?

A. Zoals op veel andere locaties het geval was, realiseerden we ons dat ons grote PIC/Math Computer Lab (75 zitplaatsen) slechts een fractie van het beschikbare CPU-vermogen gebruikte. In plaats van al die cycli verloren te laten gaan, hebben we naar een aantal gedistribueerde computerprojecten gekeken en vastgesteld dat GIMPS het beste bij ons paste. Naast het feit dat GIMPS een op wiskunde gebaseerd project is, ontdekten we dat het zeer goed geschreven was en de niet-gegradueerde computergebruikers niet hinderde (dit gold niet voor sommige van de andere projectsoftware die we onderzochten).

Het computer programma (PIC)trekt studenten van majors over de hele campus, dus het was voor ons belangrijk dat computerprojecten in het hele laboratorium begrijpelijk zouden zijn voor alle betrokkenen. GIMPS voldeed hier zeker aan de verwachtingen, en als bonus dachten we dat de informele competitie tussen GIMPS-sites interessant zou zijn voor onze studenten om te volgen, en om hun bewustzijn van Computationele Wiskunde te vergroten.

V. Wat heb je gedaan om dit uit te voeren? Was het ingewikkeld?

A. De GIMPS Prime95-software is heel eenvoudig vanuit systeembeheerperspectief. Het is eenvoudig te installeren en vereist geen onderhoud.

De Prime95-software geeft regelmatig updates over de verwerkingsstatus naar de centrale Primenet-computers. Als de machine waarop hij draait uitvalt, zullen de berekeningen opnieuw beginnen waar ze gebleven waren wanneer de computer weer opstart. Als een individuele box voor langere tijd niet beschikbaar is, zal Primenet het nummer terugvorderen en aan iemand anders toewijzen, en een nieuw nummer toewijzen wanneer de machine weer in gebruik wordt genomen.

V. Hoe werkt verificatie?

A. Wanneer een Mersenne Prime wordt gevonden, wordt er pas een formele aankondiging gedaan als een onafhankelijke derde partij de claim valideert. Bij uitzonderlijk grote getallen als deze is er altijd een kleine kans op een rekenprobleem met het gebruikte algoritme, of met de CPU van de computer zelf (het Intel Floating Point Problem)is hiervan een klassiek voorbeeld).

Vanwege deze potentiële problemen worden Mersenne Primes altijd gevalideerd met een heel ander algoritme op een computer met een andere architectuur. De verificatie kan twee weken of langer duren.

V. Wanneer vond de ontdekking plaats? Welk soort computer werd gebruikt?

A. De UCLA Mersenne Prime werd op 23 augustus 2008 gemeld op een computer met de naam zeppelin.pic.ucla.edu, een Dell Optiplex 745 met Windows XP en een Intel Core 2 Duo E6600 CPU met een snelheid van 2,4 GHz. De naam "zeppelin" maakte deel uit van onze Classic Rock Band-computerserie.

V. Hoe zit het allemaal met prijzengeld?

A. De Electronic Frontier Foundation(EFF), de belangrijkste organisatie voor burgerlijke vrijheden op internet, sponsort de Cooperative Computing Awards. Deze prijzen zijn bedoeld om "gewone internetgebruikers aan te moedigen bij te dragen aan het oplossen van grote wetenschappelijke problemen", en omvatten prijzengeld wanneer bepaalde benchmarks worden bereikt.

De EFF kent een vaste beloning van $100.000 voor het eerste priemgetal met 10 miljoen cijfers dat ontdekt moet worden. De UCLA Mersenne Prime heeft bijna 12,9 miljoen cijfers en voldoet aan de gunningscriteria. Zodra de formele resultaten in een geschikt tijdschrift zijn gepubliceerd, wordt de prijs uitgereikt. Dit zal op zijn vroegst in 2009 zijn.

Op basis van een reeds bestaande overeenkomstgaat slechts 50% van de prijs naar de ontdekker van het 10 miljoen cijferige priemgetal. 25% is bestemd voor liefdadigheid, en als erkenning van het collaboratieve karakter van GIMPS zal het grootste deel van de resterende 25% naar de ontdekkers van andere Mersenne Primes gaan, terwijl een klein bedrag naar GIMPS zelf gaat.

V. Wat hoor ik over een poster? Komt er een voor de UCLA Mersenne Prime?

A. Jarenlang heeft een bedrijf met de naam Perfectly Scientific een poster gemaakt van het grootste expliciete priemgetal dat momenteel bekend is. De poster voor M44, geproduceerd in 2006, gebruikte een extreem klein lettertype om 9,8 miljoen cijfers op een enkele poster van 29 bij 40 inch te persen. Het bedrijf bood samen met de poster een juweliersloep aan, zodat deze kon worden gelezen.

Richard Crandall van Perfectly Scientific nam onlangs contact met mij op om mij te laten weten dat de UCLA Mersenne Prime-poster nu te koop is. Het kost $ 99, zonder lijst, en is verkrijgbaar op de Perfectly Scientific-website.

V. Hoe zit het met de andere onlangs ontdekte Mersenne Prime?

A. Twee weken nadat de UCLA Mersenne Prime was ontdekt, werd nog eens 10 miljoen cijfers plus Mersenne Prime ontdekt door Hans-Michael Elvenich in Duitsland. Met 11,2 miljoen cijfers is het ongeveer 10% kleiner dan de UCLA Mersenne Prime.

Dit is niet de eerste keer dat Mersenne Primes buiten gebruik zijn ontdekt. In 1988 ontdekten Colquitt en Welsh een Mersenne Prime die kleiner was dan de vorige twee, ontdekt in 1983 en 1985.

Op het moment dat dit artikel wordt geschreven, wordt de UCLA Mersenne Prime beschouwd als de 46e Mersenne Prime (door de Mersenne Prime-zoekende gemeenschap "M46" genoemd), ook al was het de 45e die werd ontdekt. Elvenich's Mersenne Prime is M45, maar was de 46e ontdekt!

Als verdere complicatie zijn niet alle potentiële priemgetallen tussen M39 (ontdekt in 2001) en de UCLA Mersenne Prime getest, dus er zouden er in de toekomst meer kunnen worden gevonden in dat bereik. Als dat zo is, wordt de UCLA Prime "gepromoveerd" tot M47.