Digert primtall

[atlazor]

Jeg leste i en artikkel på forskning.no at en mann med navnet Josh Findley hadde funnet det største primtallet noen sinne.
Her er artikkelen:
http://www.forskning.no/Artikler/2004/j ... 6684538.53

Jeg stusset litt på om det var vanskelig å finne dette høye primtallet og begynte å se litt nærmere på bl.a. Mersenne-primtallene.
Litt senere lagde jeg noen script for å prøve å finne noen høye primtall selv, men fant fort ut at det tok veldig mye maskinresusser.
Det første scripte mitt sjekket tall mellom 1-1000 om de var primtall og skrev ut det høyeste.
Så satt jeg primtallet inn i Mersenne formelen:
2^n-1.
Det var her jeg oppdaget at Mersenne formelen trengte et primtall for å produsere et primtall. Der kom ideen om å flette denne formelen flere ganger inn i hverandre. F.eks:
2^(2^(2^n-1)-1)-1
Da fikk jeg veldig fort høye primtall, som så klart ikke kunne skrives p.g.a. størrelsen.

Men kan dette bli godkjent som et høyt primtall?
I artikkelen ble jo tallet til Josh Findley skrevet som "to opphøyd i 24 036 583 minus én" som da er 2^24036583-1.

Kan f.eks. 2^(2^(2^13-1)-1)-1 bli godkjent som et primtall?

Og er det noen andre som har noen forslag til hvordan vi kan finne et primtall større en det til Josh Findley?

[daofeishi]

Problemet er at selv om eksponenten må være prim for at resultatet skal bli et primtall, betyr ikke det at resultatet vil være prim når eksponenten er prim.

Se på følgende eksempel:

[tex]2^{11}-1 = 2047 = 23\cdot 89[/tex]

Du må dermed prøve å faktorisere tallet ditt over for å sjekke om det faktisk er et primtall.

For å finne et primtall i den størrelsesordenen, må du nok researche primalitetstestingsalgoritmer. Jeg regner med, uten å ha lest artikkelen, at fyren har brukt en av de virkelig raske probabilitetsalgoritmene, sammen med en "litt over gjennomsnittlig rask" computer.

[atlazor]

Takk for svaret =)

Ja var ganske mange datamaskiner som hadde jobbet sammen for å finne svaret, og brukte 14 dager med en helt vanelig PC for å sjekke om tallet var et primtall.
Skal se litt videre på dette, og si ifra om jeg finner noe svar.

[Klaus Knegg]

Lagde en algoritme som ga meg primtall nr. 150 000 000 etter litt over to timer. Kunne sikkert latt den stå litt lenger, men hva er vitsen? Mine 10 sifre er fortsatt latterlig langt unna 7 millioner. Må finnes bedre måter å gjøre dette på, vel?

[sEirik]

Men den artikkelen er fra 2004 da. Siste rekorden er [tex]2^{32582657}-1[/tex] som er det største kjente primtallet, og ble bevist prim i september 2006. Det er vel en test som heter Lucas-Lehmer-testen som blir mye brukt; du kan lese masse om dette på wikipedia.

http://en.wikipedia.org/wiki/Largest_known_prime

Sitat fra den siden:

Because the FFT implementation of the Lucas–Lehmer test for Mersenne numbers is faster than other primality tests for other kinds of primes, many of the largest known primes are Mersenne primes. As of January 2007 there were seven Mersenne primes among the ten largest known primes.[2] The last 13 record primes were Mersenne primes. Before that was a single non-Mersenne (improving the record by merely 37 digits in 1989), and 17 more Mersenne primes going back to 1952.[3]

The use of electronic computers has accelerated the discoveries and found all records since 1951. The record passed one million digits in 1999, earning a $50,000 prize.[4]

As of August 2007, the largest known prime was discovered by the distributed computing project Great Internet Mersenne Prime Search (GIMPS):
2^32,582,657 − 1.

This was confirmed to be a prime number on September 11, 2006. This number is 9,808,358 digits long and is the 44th known Mersenne prime.

Its predecessor as largest known prime, 2^30,402,457 − 1, was first shown to be prime on December 15, 2005 by GIMPS also. GIMPS found the 10 latest records on ordinary computers operated by participants around the world.

There is a $100,000 prize for the first known prime with at least 10,000,000 digits. It seems likely that this prize will be given to the next record prime as the current record is close to this mark. A Mersenne prime 2^p − 1 with p ≥ 33,219,281 would have at least 10,000,000 digits, and GIMPS is testing many candidates of this size.

Så det er store summer ute og går her for de som er interessert i å jakte på primtall

Hvem som helst kan forresten laste ned programmet til GIMPS og la det kjøre i bakgrunnen på datamaskinen; det vil da bruke kun av de ledige maskinressursene slik at annen programvare ikke går tregere. Hvis du er heldig og oppdager et primtall ved å kjøre GIMPS på maskinen din, så er det du som får premien. Sånn jeg har forstått det.

[daofeishi]

Lagde en algoritme som ga meg primtall nr. 150 000 000 etter litt over to timer.

Mathematica ga meg primtall nr 150 000 000 etter under et halvt sekund. Tallet er 3121238909

Må finnes bedre måter å gjøre dette på, vel?

Så spørsmål besvart De raskeste primtallssjekkmetodene er probabilistiske; Eirik har vel linka videre til noe nyttig.

[mrcreosote]

Jeg regna det huet og fikk det samme. Brukte riktignok 4 sekunder da.

[Emilga]

Hva er vitsen med å finne så store primtall?
Jeg vet at de bruke i såkalte Public Key krypteringer, men det må da finnes en grense på hvor store primtallen kan være før det blir ineffektivt?
Er det bare for å vise at "min tiss er større enn din tiss"?
(Jeg ser selvsagt bort fra de $100.000 nå )

[sEirik]

Er det bare for å vise at "min tiss er større enn din tiss"?

Du har skjønt det.

[mrcreosote]

Dere kara som har peil på dette: Jeg har lest, som dao nevner, at disse raske testene gir korrekt svar med sannsynlighet 1-eps og ikke 1. Advokaturet for dette var at det var større sannsynlighet for at det var noe feil med datamaskinene som regna enn at testen faktisk ville slå ut feil. Har jeg forstått ting riktig?

I såfall: Er ikke dette veldig merkelig? Man leker ikke matematiker heller, testen bør beviselig være nøyaktig for at den skal kunne forsvares. Argumentet om at det heller er en kortslutning i maskina en plass er fullstendig urimelig og har ingenting med matematikk å gjøre.

Jeg hadde satt pris på en liten utdypning eller noen gode linker til saker om dette.

Your dick is smaller than any [tex]\eps[/tex]>0.

[Charlatan]

Ville det ikke være fornuftig å dobbeltsjekke eventuelle primtall du finner?

[sEirik]

Det som vil være fornuftig er jo å lete etter tall som har ganske stor sannsynlighet for å være primtall, ved å bruke en rask algoritme. Hvis man finner et slikt tall, kan man sjekke helt sikkert om det er primtall eller ikke ved å bruke en litt tregere, men helt korrekt algoritme.

[TurboN]

en veldig enkel algoritme:

for(int i=2; i<=(tallet_man_undersøker)/2; i++)
{
if(tallet_man_undersøker % i = 0) return "ikke primtall"
}
return "primtall"

man kan jo speede det opp, ved å teste på 2, derav eliminere alle heltall om tallet ikke har 2 som en faktor

samme med 3, fjerne alle muligheter tall som har 3 som faktor osv...

kan implementeres i en trestruktur, eller en skiplist elns

[sEirik]

Men den enkleste måten å speede opp testen på, er å la i være bare oddetall (og selvfølgelig også 2, først). Dessuten trenger man ikke å sjekke for faktorer som er større enn kvadratroten av tallet man vil teste.

[ingentingg]

Dere kara som har peil på dette: Jeg har lest, som dao nevner, at disse raske testene gir korrekt svar med sannsynlighet 1-eps og ikke 1. Advokaturet for dette var at det var større sannsynlighet for at det var noe feil med datamaskinene som regna enn at testen faktisk ville slå ut feil. Har jeg forstått ting riktig?

I såfall: Er ikke dette veldig merkelig? Man leker ikke matematiker heller, testen bør beviselig være nøyaktig for at den skal kunne forsvares. Argumentet om at det heller er en kortslutning i maskina en plass er fullstendig urimelig og har ingenting med matematikk å gjøre.

Jeg hadde satt pris på en liten utdypning eller noen gode linker til saker om dette.

Your dick is smaller than any [tex]\eps[/tex]>0.

Kan jo kommentere litt om det eg veit.
For å bli erklært verdens største primtall, må det være bevist at det er prim, det holder ikke med sannsynlighet.

Der det derimot holder med sannsynlighet er innenfor kodeteori.
RSA-koden og mange andre koder bruker store primtall for å kryptere beskjeder. For å finne disse primtallene bruker man såkalte probalistiske metoder, som finner primtall med en sannsynlighet som er meget stor, f.eks 1-eps (eps ved 64-bit tallsystem er 2^-23).
Dette vil da holde, siden sjansen for at noen skulle prøve å knekke den ene koden som ikke er "sikker" er veldig liten.