Største kjente primtall oppdaget: Hvorfor det betyr noe

I filmen Contact, basert på romanen med samme navn av Carl Sagan, søker Dr. Ellie Arroway etter intelligent utenomjordisk liv ved å skanne himmelen med radioteleskoper. Når Arroway, spilt av Jodie Foster, gjenkjenner primtall i et interplanetært signal, mener hun det er et bevis på at en fremmed intelligens har sendt menneskeheten en melding.

Et tall regnes som prime hvis det bare kan deles av en og seg selv. For eksempel er to, tre, fem og syv prime. Tallet 15, som er tre ganger fem, er ikke prime. Det er ikke tilfeldig at Arroway mener at romvesenene i Contact bruker primtall som et kosmisk «hei» – de er byggesteiner med andre tall. Hvert tall er et produkt av primtall.

I desember 2017, det største kjente primtall ble oppdaget ved hjelp av et datasøk. Primet ble oppdaget av Jonathan Pace, en elektroingeniør som for tiden jobber i FedEx. Hvorfor er dette viktig? For uten primtall kan bankinformasjonen din, PayPal-transaksjoner eller Amazon-kjøp bli kompromittert.

Store primtelefoner, som den nettopp oppdagede, spiller en kritisk rolle i cybersikkerhet. Kryptografi er vitenskapen om koding og dekoding av informasjon, og mange av algoritmene, for eksempel RSA, er sterkt avhengige av primtall.

Mersenne-primtall

Selv om det er uendelig mange primtall, er det ingen kjent f ormula for å generere dem alle. Et løp pågår for å finne større primtall ved hjelp av en blanding av matteknikker og beregning.

En måte å få store premier på, bruker et matematisk konsept oppdaget av den franske munken og forskeren fra det 17. århundre, Marin Mersenne.

En Mersenne prime er en av formen 2ⁿ – 1, hvor n er et positivt heltall. De fire første av disse er tre, syv, 31 og 127.

Ikke alle tall i formen 2ⁿ – 1 er imidlertid primtall; for eksempel 2⁴ – 1 = 15. Hvis 2ⁿ – 1 er prime, kan det vises at n selv må være prime. Men selv om n er prime, er det ingen garanti for at tallet 2ⁿ – 1 er prime: 2¹¹ – 1 = 2.047, som ikke er prime fordi det tilsvarer 23 ganger 89.

Det er bare 50 kjente Mersenne-primtall . En uløst antagelse er at det er uendelig mange av dem.

Jakten på nye primtall

The Great Internet Mersenne Prime Search (eller GIMPS) er et samarbeid mellom mange individer og lag fra hele verden for å finne nye Mersenne-primtall. George Woltman startet GIMPS i 1996, og i 2018 inkluderer den mer enn 183.000 frivillige brukere som bidrar med samlet kraft på over 1,6 millioner CPUer.

Den sist oppdagede Mersenne prime er kortfattet skrevet som 2⁷⁷²³²⁹¹⁷ – 1; det er to ganget med seg selv 77 232 917 ganger, minus en. Jonathan Paces oppdagelse tok seks dagers beregning på en firekjerners Intel i5-6600-prosessor, og ble uavhengig verifisert av fire andre grupper.

Den nylig oppdagede primæren har hele 23 249 425 sifre. For å få en følelse av hvor stort det er, antar vi at vi fylte opp en bok med sifre, hvert siffer telles som et ord og hver bok har 100 000 ord. Da ville sifrene på 2⁷⁷²³²⁹¹⁷ – 1 fylle opp rundt 232 bøker!

Hvordan finner GIMPS primtall?

GIMPS bruker Lucas-Lehmer-testen for primtall. For dette, danner en sekvens av heltall som begynner med fire, og hvis vilkår er forrige begrep i kvadrat og minus to. Testen sier at tallet 2ⁿ – 1 er primært hvis det deler den (n-2) termen i sekvensen.

Mens Lucas-Lehmer-testen ser enkel ut til å sjekke, er beregningsflaskehalsen ved bruk av det kommer fra kvadratiske tall. Multiplikasjon av heltall er noe hvert barn i skolealderen kan gjøre, men for store tall gir det problemer, selv for datamaskiner. En vei rundt dette er å bruke Fast Fourier Transforms (FFT), algoritmer som fremskynder beregningene.

Alle kan bli involvert i GIMPS – så lenge du har en anstendig datamaskin med internettforbindelse. Gratis programvare for å søke etter Mersenne-primtall kan du finne på GIMPS-nettstedet.

Selv om den største kjente prime er utrolig massiv, er det uendelig mange flere primtall utover det som venter på å bli oppdaget. Som Ellie Arroway gjorde i Contact, trenger vi bare å lete etter dem.