UCLA Mersenne Prime

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

I augusti 2008 upptäcktes ett nytt Mersenne-primtal på en av datorerna som tillhörde UCLA Mathematics Departments Program in Computing (PIC). Detta nummer visar sig vara världens största kända primtal, och upptäckten har genererat stort intresse. I ett försök att spara tid och energi för alla tänkte jag lägga upp lite information på webben i FAQ-format.

Eftersom ett antal av frågorna jag har fått har kommit från personer med icke-teknisk bakgrund (inklusive barn), är denna FAQ icke-teknisk. Du måste dock veta vad ett primtal är.

Jag är dock tvungen att ge denna varning: även om jag arbetar för matematikavdelningen, är jag en systemadministratör, inte en matematiker! Om du letar efter seriös Mersenne Prime-information hänvisar jag dig till Chris Caldwells utmärkta webbplats Mersenne Primes: History, Theorems and Lists. Andra intressanta platser inkluderar Wolframs Mersenne Prime-sida och Landon Curt Nolls underhållande Mersenne Prime Digits and Names.

Nu till frågorna!

F. Så vad är en Mersenne Prime?

S. Kort sagt, det finns en viss underklass av primtal som kallas Mersenne Primes. De är uppkallade efter Marin Mersenne, en matematiker från 1600-talet. När detta skrivs finns det färre än 50 kända Mersenne Primes.

Mersenneprimtal har alla formen av 2P -1, där P är ett känt primtal. Den första Mersenne Prime är 3 eftersom 22 -1 = 3. Observera att exponenten P är ett primtal, i detta fall 2. Nästa Mersenne Prime är 7 eftersom 2 3 - 1 = 7, där P är primtalet 3. Därefter kommer 31 (2 5 - 1), sedan 127 (2 7 - 1), 8191 (2 13- 1) och 131071 (2 17 - 1).

Som du kan se, efter de första, blir Mersenne Primes stora väldigt snabbt. Det finns en fin tabell över de kända Mersenne Primes här som kommer att ge lite perspektiv.

Det minsta av dessa antal var kända under antiken, men så sent som 1951 hade endast 12 upptäckts. Under de senaste 50 åren har flera dussin fler upptäckts med hjälp av datorer. De senast upptäckta Mersenne Primes är häpnadsväckande stora, med miljontals siffror. UCLA Mersenne Prime är cirka 12,9 miljoner siffror lång.

Observera att alla Mersenneprimtal är primtal, men väldigt få primtal är Mersenneprimtal.

F. Vad är UCLA Mersenne Prime? Varför är det speciellt?

S. UCLA Mersenne Prime är det första primtal som upptäckts som har över 10 miljoner siffror. Den upptäcktes vid UCLA Mathematics-avdelningen den 23 augusti 2008.

Alla Mersenne Primes är speciella eftersom de är så sällsynta, men den här har fått extra uppmärksamhet eftersom den kvalificerar sig för ett pris (se nedan).

UCLA Mersennes primtal är 2 43112609 - 1. Det faktiska numret har 12 978 189 siffror. Om du är så benägen har den mångårige Mersenne Prime-forskaren Landon Curt Noll gjort själva numret tillgängligt här. Om du är riktigt, riktigt benägen, tillhandahåller han också hela numret på engelska (alla 328 megabyte av det) här.

F. Är detta UCLA:s första Mersenne Prime?

S. Det här är faktiskt UCLA:s åttonde Mersenne Prime!

1952 hittade professor Raphael Robinson 5 nya Mersenne Primes med hjälp av UCLA:s Standards Western Automatic Computer (SWAC), en av sin tids snabbaste datorer. Dessa var den 13:e till 17:e Mersenne Primes som upptäcktes, och var och en hade hundratals siffror. Robinsons Mersenne Primes var de första som hittades på 75 år och de första som upptäcktes med hjälp av en digital dator.

År 1961 upptäckte UCLA-matematikern Alexander Hurwitz den 19:e och 20:e Mersenne Primes på UCLA Computer Centers IBM 7090 stordator. Vart och ett av dessa nummer hade över 1200 siffror.

Nu, 47 år senare, fortsätter UCLA-traditionen att hitta Mersenne Primes!

F. Vem letar efter Mersenne Primes? Hur går de till väga?

S. Tusentals människor som använder tiotusentals datorer deltar i Great Internet Mersenne Prime Search (GIMPS), en organiserad insats tillägnad sökandet efter Mersenne Primes. Detta är en av många pågående ansträngningar inom området distribuerad datoranvändning, och utan tvekan den mest framgångsrika.

Sökandet är mycket välorganiserat. De goda människorna på Primenet har koordinerat insatserna under de senaste 12 åren och tillhandahåller den utmärkta Prime95programmet gratis för alla som vill köra det. De håller reda på vilka nummer som har testats och ger en stadig ström av oprövade kandidatnummer till GIMPS-communityt. GIMPS-deltagare rankas efter deras produktivitet. Du kan hitta oss under namnet UCLA_Math; vi är vanligtvis rankade någonstans mellan 40:e och 55:e plats.

Det kan ta en enda maskinmånader att testa bara ett kandidatnummer, men genom att utnyttja kraften hos internetanslutna enskilda datorer över hela världen kan snabba framsteg göras.

F. Vad är oddsen för att upptäcka en Mersenne Prime?

S. Enligt GIMPS-projektet oddsen för att något kandidatnummer kommer att visa sig vara ett Mersenne Prime är 1 på 150 000.

F. Hur testar man faktiskt siffror för att se om de är Mersenne Primes?

S. Det finns många tal av formen 2P - 1, men bara ett fåtal av dem är Mersenne Primes. Det finns ett antal tekniker för att testa dessa tal för att se om de är Mersenne-primtal, men den första metoden är att försöka faktorisera kandidatexponenten, P, och sedan försöka faktorisera kandidatprimtal, 2P -1, med hjälp av några små primtal.

Det finns en 75 år gammal algoritm som heter Lucas-Lehmer-testet som är allmänt erkänt som det bästa verktyget för att testa Mersenne Primes. Prime95-programmet använder den här metoden i stor utsträckning, liksom några andra. En förklaring ligger utanför ramen för detta dokument, men den intresserade läsaren kan lära sig mer här.

F. OK, varför letar folk efter Mersenne Primes? Vad är de bra för?

S. Av samma skäl som människor klättrar i berg, seglar på okända hav och utforskar kosmos. Det är en utmaning! Det är spännande att driva på beräkningsmatematikens hölje och att söka efter något okänt som du tror finns där ute. Som bonus, till skillnad från gamla upptäcktsresande, får vi sitta i bekväma kontorsstolar medan vi letar!

Detta är inte att säga att det inte finns något matematiskt värde i Mersenne Primes. De är verkligen av värde inom kryptografi och kan ha andra användningsområden som ännu inte har upptäckts.

Primtalsforskaren Chris Caldwell utforskar denna fråga mer djupgående i sin artikel "Varför hittar människor dessa primtal?".

F. Förutom utmaningen, varför valde du att delta?

S. Som har varit fallet på många andra platser insåg vi att vårt stora (75 platser) PIC/Math Computer Lab bara använde en bråkdel av sin tillgängliga CPU-kraft. Istället för att låta alla dessa cykler gå till spillo tittade vi på ett antal distribuerade datorprojekt och fastställde att GIMPS passade oss bäst. Förutom att det var lämpligt att GIMPS är ett matematikbaserat projekt, fann vi att det var mycket välskrivet och inte störde datoranvändarna på grundutbildningen (detta gällde inte en del av de andra projektprogramvaran vi undersökte).

Programmet i datoring (PIC)drar studenter från huvudämnen över hela campus, så det var viktigt för oss att alla labbomfattande datorprojekt var begripliga för alla berörda. GIMPS passade verkligen räkningen här, och som en bonus trodde vi att den informella konkurrensen mellan GIMPS-sajter skulle vara intressant för våra elever att följa, och öka deras medvetenhet om beräkningsmatematik.

F. Vad gjorde du för att köra detta? Var det komplicerat?

S. GIMPS Prime95-programvaran är mycket enkel ur ett systemadministrativt perspektiv. Det är lätt att installera och kräver inget underhåll.

Prime95-mjukvaran skickar regelbundna uppdateringar om dess bearbetningsstatus till de centrala Primenet-datorerna. Om maskinen som körs på går ner kommer beräkningarna att starta igen där de slutade när datorn kommer upp igen. Om en enskild box är nere under en längre period kommer Primenet att återta numret och tilldela det till någon annan, och tilldela ett nytt nummer när maskinen återgår till drift.

F. Hur fungerar verifiering?

S. När en Mersenne Prime hittas görs inte ett formellt tillkännagivande förrän en oberoende tredje part validerar anspråket. Med exceptionellt stora siffror som dessa, finns det alltid en liten chans för ett beräkningsproblem med algoritmen som används eller med själva datorns CPU (Intel Floating Point Problemär ett klassiskt exempel på detta).

På grund av dessa potentiella problem valideras Mersenne Primes alltid med en helt annan algoritm på en dator med en annan arkitektur. Verifieringen kan ta två veckor eller längre.

F. När inträffade upptäckten? Vilken typ av dator användes?

S. UCLA Mersenne Prime rapporterades den 23 augusti 2008 på en dator som heter zeppelin.pic.ucla.edu, en Dell Optiplex 745 som kör Windows XP med en Intel Core 2 Duo E6600 CPU som körs på 2,4 GHz. Namnet "zeppelin" var en del av vår Classic Rock Band-serie av datorer.

F. Vad handlar det här om prispengar?

S. Electronic Frontier Foundation(EFF), Internets främsta organisation för medborgerliga friheter, sponsrar Cooperative Computing Awards. Dessa utmärkelser är avsedda att "uppmuntra vanliga internetanvändare att bidra till att lösa enorma vetenskapliga problem", och har prispengar när vissa riktmärken uppnås.

EFF har en stående utmärkelse på $100 000 för det första primtalet med 10 miljoner siffror som ska upptäckas. UCLA Mersenne Prime har nästan 12,9 miljoner siffror och uppfyller tilldelningskriterierna. När de formella resultaten har publicerats i en lämplig tidskrift kommer priset att delas ut. Detta kommer att vara tidigast 2009.

Genom redan existerande överenskommelse, endast 50 % av priset kommer att gå till upptäckaren av 10 miljoner siffror. 25 % är öronmärkta för välgörenhet, och som ett erkännande av GIMPS samarbetsvilja kommer huvuddelen av de återstående 25 % att gå till upptäckarna av andra Mersenne Primes, med en liten summa till GIMPS själv.

F. Vad är det här jag hör om en affisch? Kommer det att finnas en för UCLA Mersenne Prime?

S. I flera år har ett företag som heter Perfectly Scientific skapat en affisch med det största för närvarande kända explicita primtalet. Affischen för M44, producerad 2006, använde ett extremt litet typsnitt för att klämma in 9,8 miljoner siffror på en enda 29" gånger 40" affisch. Företaget erbjöd en juvelerares lupp tillsammans med affischen bara för att den skulle kunna läsas.

Richard Crandall från Perfectly Scientific kontaktade mig nyligen för att meddela mig att UCLA Mersenne Prime-affischen nu finns att köpa. Det kostar $99, utan ram och finns tillgängligt på webbplatsen Perfectly Scientific.

F. Hur är det med den andra nyligen upptäckta Mersenne Prime?

S. Två veckor efter att UCLA Mersenne Prime upptäcktes upptäcktes ytterligare 10 miljoner siffror plus Mersenne Prime av Hans-Michael Elvenich i Tyskland. Med 11,2 miljoner siffror är den cirka 10 % mindre än UCLA Mersenne Prime.

Det är inte första gången som Mersenne Primes har upptäckts ur funktion. 1988 upptäckte Colquitt och Welsh en Mersenne Prime mindre än de två föregående, upptäckte 1983 och 1985.

När detta skrivs anses UCLA Mersenne Prime vara den 46:e Mersenne Prime (kallad "M46" av Mersenne Prime-sökanden), även om det var den 45:e som upptäcktes. Elvenichs Mersenne Prime är M45, men var den 46:e som upptäcktes!

Som en ytterligare komplikation har inte alla potentiella primtal mellan M39 (upptäckt 2001) och UCLA Mersenne Prime testats, så det kan finnas fler i det intervallet vid ett framtida datum. Om de är det kommer UCLA Prime att "befordras" till M47.