UCLA Mersenne Prime

Originaal artikkel: https://www.math.ucla.edu/~edson/prime/

2008 aasta augustis avastati ühest UCLA matemaatikaosakonna arvutiprogrammi (PIC) kuuluvast arvutist uus Mersenne'i peanumber. See arv osutub maailma suurimaks teadaolevaks algarvuks ja avastus on tekitanud palju huvi. Püüdes säästa kõigi aega ja energiat, mõtlesin, et panen mõne teabe veebi KKK-vormingus.

Kuna mitmed mulle esitatud küsimused on tulnud mittetehnilise taustaga inimestelt (sealhulgas lastelt), on see KKK mittetehniline. Siiski peate teadma, mis on algarv.

Olen siiski sunnitud pakkuma selle hoiatuse: kuigi ma töötan matemaatikaosakonnas, olen ma süsteemiadministraator, mitte matemaatik! Kui otsite tõsist Mersenne Prime'i teavet, viitan teile Chris Caldwelli suurepärasele veebisaidile Mersenne Primes: History, Theorems and Lists. Muude huvitavate saitide hulka kuuluvad Wolframi Mersenne Prime'i leht ja Landon Curt Nolli meelelahutuslik Mersenne'i peanumbrid ja nimed.

Nüüd aga küsimuste juurde!

K. Mis on siis Mersenne Prime?

V. Lühidalt öeldes on olemas teatud algarvude alamklass, mida nimetatakse Mersenne'i algarvudeks. Need on nime saanud 17. sajandi matemaatiku Marin Mersenne'i järgi. Selle kirjutamise ajal on Mersenne Primesid teada vähem kui 50.

Mersenne'i algarvud on kõik kujul 2 P -1, kus P on teadaolev algarv. Esimene Mersenne'i algarv on 3, sest 2 2 -1 = 3. Pange tähele, et eksponent P on algarv, antud juhul 2. Järgmine Mersenne'i alamarv on 7, sest 2 3 - 1 = 7, kusjuures P on algarv 3 Järgmisena tuleb 31 (2 5 - 1), seejärel 127 (2 7 - 1), 8191 (2 13- 1) ja 131071 (2 17 - 1).

Nagu näete, muutuvad Mersenne Primes pärast esimest paari väga kiiresti suureks. Siin on kena tuntud Mersenne Primesi tabel, mis annab perspektiivi.

Väikseim neist arvudest oli teada antiikajal, kuid veel 1951. aastal oli avastatud vaid 12. Viimase 50 aasta jooksul on arvutite abil avastatud veel mitukümmend. Viimati avastatud Mersenne Primes on hämmastavalt suured, miljonite numbritega. UCLA Mersenne Prime on umbes 12,9 miljonit numbrit pikk.

Pange tähele, et kõik Mersenne'i algarvud on algarvud, kuid väga vähesed algarvud on Mersenne'i algarvud.

K. Mis on UCLA Mersenne Prime? Miks see eriline on?

V. UCLA Mersenne Prime on esimene avastatud algnumber, millel on üle 10 miljoni numbri. See avastati UCLA matemaatikaosakonnas 23. augustil 2008.

Kõik Mersenne'i algarvud on erilised, kuna need on nii haruldased, kuid see on pälvinud erilist tähelepanu, kuna see kvalifitseerub auhinnale (vt allpool).

UCLA Mersenne'i põhinumber on 2 43112609 - 1. Tegelik number koosneb 12 978 189 numbrist. Kui olete nii valmis, on Mersenne'i peaministri kauaaegne uurija Landon Curt Noll teinud numbri siin kättesaadavaks . Kui sa tõesti tahad, annab ta siinka kogu numbri inglise keeles (kõik 328 megabaiti).

K. Kas see on UCLA esimene Mersenne Prime?

V. Tegelikult on see UCLA kaheksas Mersenne Prime!

1952. aastal leidis professor Raphael Robinson UCLA Standards Western Automatic Computer (SWAC) abil 5 uut Mersenne Primesi , mis on üks oma aja kiiremaid arvuteid. Need olid 13.–17. avastatud Mersenne'i algarvud ja igaühel neist oli sadu numbreid. Robinsoni Mersenne Primesid olid esimesed, mis leiti 75 aasta jooksul, ja esimesed, mis avastati digitaalse arvuti abil.

1961. aastal avastas UCLA matemaatik Alexander Hurwitz UCLA arvutikeskuse IBM 7090 suurarvutilt 19. ja 20. Mersenne'i algarvu. Igas neist numbritest oli üle 1200 numbri.

Nüüd, 47 aastat hiljem, jätkub UCLA traditsioon Mersenne Primesi leidmiseks!

K. Kes otsib Mersenne Primesi? Kuidas neil sellega läheb?

V. Tuhanded inimesed, kes kasutavad kümneid tuhandeid arvuteid, osalevad Great Internet Mersenne Prime Searchis (GIMPS), mis on Mersenne Primesi otsimisele pühendatud organiseeritud ettevõtmine. See on üks paljudest jätkuvatest jõupingutustest hajutatud andmetöötluse valdkonnas ja vaieldamatult kõige edukam.

Otsing on väga hästi korraldatud. Primeneti head inimesed on koordineerinud jõupingutusi viimased 12 aastat ja pakuvad suurepärast Prime95programm tasuta kõigile, kes soovivad seda käivitada. Nad jälgivad, milliseid numbreid on testitud, ja pakuvad GIMPS-i kogukonnale pidevat testimata kandidaatnumbrite voogu. GIMPS-i osalejad järjestatakse nende produktiivsuse järgi . Leiate meid UCLA_Mathi nime all ; oleme tavaliselt kuskil 40. ja 55. koha vahel.

Vaid ühe kandidaatnumbri testimiseks võib kuluda mitu kuud, kuid Interneti-ühendusega üksikute arvutite võimsuse ärakasutamine üle kogu maailma on võimalik saavutada kiireid edusamme.

K. Kui suur on Mersenne Prime'i avastamise tõenäosus?

V. Vastavalt GIMPS-i projektile tõenäosus, et mis tahes kandidaadi number osutub Mersenne'i peaministriks, on 1:150 000.

K. Kuidas te tegelikult numbreid testite, et näha, kas need on Mersenne Primesid?

V. Vormiga 2 P - 1 on palju numbreid, kuid ainult väga vähesed neist on Mersenne Primesid. Nende arvude testimiseks, et näha, kas need on Mersenne'i algarvud, on mitmeid meetodeid, kuid esialgne meetod on püüda faktoriteerida kandidaateksponenti P ja seejärel katsetada kandidaadi algarvu 2 P -1 , kasutades mõned väikesed algarvud.

Seal on 75 aastat vana algoritm, mida nimetatakse Lucas-Lehmeri testiks, mis on laialdaselt tunnustatud kui parim tööriist Mersenne Primesi testimiseks. Programm Prime95 kasutab seda meetodit ja ka mõnda muud laialdaselt. Selgitus ei kuulu selle dokumendi ulatusse, kuid huvitatud lugeja saab siitrohkem teada.

K. OK, miks inimesed Mersenne Primesi otsivad? Milleks need head on?

V. Samadel põhjustel, miks inimesed ronivad mägedesse, purjetavad tundmatutel meredel ja uurivad kosmost. See on väljakutse! Põnev on suruda arvutusmatemaatika ümbrikusse ja otsida midagi tundmatut, mis teie arvates seal on. Boonusena saame erinevalt vana aja avastajatest istuda otsimise ajal mugavates kontoritoolides!

See ei tähenda, et Mersenne Primesil pole matemaatilist väärtust. Need on krüptograafia valdkonnas kindlasti väärtuslikud ja neil võib olla veel avastamata muid kasutusvõimalusi.

Algarvude uurija Chris Caldwell uurib seda probleemi põhjalikumalt oma artiklis "Miks inimesed leiavad need algarvud?".

K. Peale väljakutse, miks otsustasite osaleda?

V. Nagu paljudel muudel saitidel, mõistsime, et meie suur (75-kohaline) PIC/Math Computer Lab kasutas vaid murdosa olemasolevast protsessori võimsusest. Selle asemel, et lasta kõigil neil tsüklitel raisku minna, vaatasime mitmeid hajutatud andmetöötlusprojekte, leides, et GIMPS sobib meile kõige paremini. Lisaks sellele, et GIMPS on matemaatikapõhine projekt, leidsime, et see oli väga hästi kirjutatud ega seganud bakalaureuseõppe arvutikasutajaid (see ei kehtinud mõne muu uuritud projektitarkvara kohta).

Arvutitöö programm (PIC) tõmbab tudengeid peamistest ülikoolidest üle kogu ülikooli, seega oli meie jaoks oluline, et kõik laboriülesed andmetöötlusprojektid oleksid kõigile asjaosalistele arusaadavad. GIMPS sobib kindlasti siinkohal ja boonusena arvasime, et mitteametlik võistlus GIMPS-i saitide vahel oleks meie õpilastele huvitav jälgida ja tõstaks nende teadlikkust arvutusmatemaatikast.

K. Mida te selle käivitamiseks tegite? Kas see oli keeruline?

V. GIMPS Prime95 tarkvara on süsteemi administreerimise seisukohast väga lihtne. Seda on lihtne paigaldada ja see ei vaja hooldust.

Prime95 tarkvara väljastab Primeneti keskarvutitele regulaarselt värskendusi oma töötlemisoleku kohta. Kui masin, millel see töötab, läheb alla, käivituvad arvutused uuesti sealt, kus need pooleli jäid, kui arvuti uuesti üles tuleb. Kui mõni üksikboks on pikemaks ajaks maas, võtab Primenet selle numbri tagasi ja määrab selle kellelegi teisele ning määrab uue numbri, kui masin uuesti kasutusele võetakse.

K. Kuidas kinnitamine töötab?

V. Kui Mersenne Prime leitakse, ei tehta ametlikku teadet enne, kui sõltumatu kolmas osapool nõude kinnitab. Selliste erakordselt suurte arvude puhul on alati väike tõenäosus, et kasutatava algoritmi või arvuti enda protsessoriga tekib arvutusprobleem (Intel ujukoma probleem on selle klassikaline näide).

Nende võimalike probleemide tõttu valideeritakse Mersenne Primesid erineva arhitektuuriga arvutis alati täiesti erineva algoritmi abil. Kinnitamine võib kesta kaks nädalat või kauem.

K. Millal avastus toimus? Millist arvutit kasutati?

V. UCLA Mersenne Prime'ist teatati 23. augustil 2008 arvutis nimega zeppelin.pic.ucla.edu , Dell Optiplex 745, milles töötab Windows XP ja Intel Core 2 Duo E6600 protsessor, mis töötab sagedusel 2,4 GHz. Nimi "tsepeliin" oli osa meie Classic Rock Bandi arvutite sarjast.

K. Mis asi see auhinnarahaga on?

V. Electronic Frontier Foundation(EFF), Interneti esmakordne kodanikuvabaduste organisatsioon, sponsoreerib Cooperative Computing Awards. Nende auhindade eesmärk on "julgustada tavalisi Interneti-kasutajaid panustama tohutute teadusprobleemide lahendamisele" ja teatud kriteeriumide saavutamisel antakse auhindu.

Euroopa Kalandusfondil on 100 000 dollari suurune alaline auhind esimese avastatud 10 miljoni numbriga algarvu eest. UCLA Mersenne Primeil on peaaegu 12,9 miljonit numbrit ja see vastab auhinna kriteeriumidele. Kui ametlikud tulemused on avaldatud vastavas ajakirjas, antakse auhind välja. See toimub kõige varem 2009. aastal.

Eelnevalkokkuleppel, vaid 50% auhinnast läheb 10 miljoni numbrilise algarvu avastajale. 25% on ette nähtud heategevuseks ja tunnustades GIMPS-i koostööpõhist olemust, läheb suurem osa ülejäänud 25% teiste Mersenne Primesi avastajatele ning väike summa läheb GIMPS-ile endale.

K. Mida ma plakati kohta kuulen? Kas see tuleb UCLA Mersenne Prime'i jaoks?

V. Ettevõte nimega Perfectly Scientific on aastaid loonud plakatit suurima praegu teadaoleva eksplitsiitse algarvuga. 2006. aastal toodetud M44 plakat kasutas äärmiselt väikest kirjatüüpi, et pigistada 9,8 miljonit numbrit ühele 29x40 tollisele plakatile. Ettevõte pakkus koos plakatiga juveliiri luupi, et seda oleks võimalik lugeda.

Richard Crandall ettevõttest Perfectly Scientific võttis minuga hiljuti ühendust, et anda teada, et UCLA Mersenne Prime'i plakat on nüüd ostmiseks saadaval. See on raamita 99 dollarit ja saadaval Perfectly Scientificu veebisaidil.

K. Kuidas on lood teise hiljuti avastatud Mersenne Prime'iga?

V. Kaks nädalat pärast UCLA Mersenne Prime'i avastamist avastas Hans-Michael Elvenich Saksamaal veel 10 miljoni numbriga pluss Mersenne Prime'i. 11,2 miljoni numbriga on see umbes 10% väiksem kui UCLA Mersenne Prime.

See ei ole esimene kord, kui Mersenne Primes avastatakse korrast ära. 1988. aastal avastasid Colquitt ja Welsh Mersenne Prime'i, mis on väiksem kui kaks eelmist, avastati aastatel 1983 ja 1985.

Selle kirjutamise ajal peeti UCLA Mersenne Prime'i 46. Mersenne'i pealinnaks (Mersenne Prime'i otsijate kogukond nimetas seda "M46"), kuigi see oli 45. avastatud. Elvenichi Mersenne Prime on M45, kuid avastati 46.!

Täiendava komplikatsioonina ei ole testitud kõiki potentsiaalseid algväärtusi M39 (avastati 2001. aastal) ja UCLA Mersenne Prime'i vahel, nii et tulevikus võib selles vahemikus olla rohkem. Kui need on nii, ülendatakse UCLA Prime M47-le.