Uusi suurin alkuluku todennäköisesti löydetty

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Vain vähän alle 10 000 000 numeron mittainen alkuluku on todennäköisesti löytynyt. Tarkistuslaskut on käynnistetty (ehkä jo suoritettukin, vaikea sanoa kun varsinainen sivu on slashdotattu).

Luku löydettiin hajautetun laskennan projektin avulla, joka pyrkii etsimään Mersennen alkulukuja. Yksi tavotteista on löytää 10 000 000 numeron mittainen alkuluku (luku on siis niin iso, että jos sen tallentaa tiedostoon, se vie noin 10 MB tilaa pakkaamattomana), jonka löytäjälle on luvattu 100 000 dollarin palkkio. Palkkio on luvassa myös 100 000 000 numeron mittaisesta alkuluvusta (150 000 dollaria) ja 1000 000 000 numeron mittaisesta alkuvusta (250 000 dollaria).

Kommentit (15)

Vierailija

Mitä ihmeellistä tossa on... mä selvittäisin vaikka 1000000000miljardin luvun alkuluvun. No tiiän että olen käsittänyt jotain väärin, mutta ei voi mitään.

Vierailija

Joku siis tutkii työkseen monimiljoonanumeroisia alkulukuja ja joku maksaa siitä satoja tuhansia euroja.

Onnea matkaan, ihmiskunta.

Vierailija

"Suurten alkulukujen löytäminen on erittäin työlästä. Vieläkään ei tunneta determinististä polynomiaikaista algoritmia jolla voitaisiin varmistaa että joku tietty alkuluku tosiaan on alkuluku. Tämä tarkoittaa että algoritmi antaisi AINA oikean tuloksen kyllä tai ei ja lisäksi se tapahtuisi ajassa n^k jossa n on annetun luvun pituus ja k on jokin vakio. Määritelmän kannalta käytetyllä lukujärjestelmällä ei ole merkitysta mutta käytännössä se on usein joko 2 kantainen binäärinen järjestelmä tai jokin kakkosen potenssi esim. 2^8 kantainen järjestelmä jolloin jokainen luvun alkio on tavu.

Tähän tehtävään on kehitetty sekä probabalistisia algoritmeja, joilla saatu ratkaisu voi olla väärä tietyllä todennäköisyydellä, sekä exponentiaalisia algoritmeja. Exponentiaalisten algoritmien ongelma on se että ne tarvitsevat erittäin suuria määriä laskentatehoa, esim.Oletetaan että n=1000 ja 1GHz prosessori laskee yhden operaation kellojaksossa, joten n^2 ajassa toimiva algoritmi kestäisi noin sekunnin kun taas 2^n algoritmi tarvitsisi noin 10^266 vuotta.

Lisäksi on olemassa algoritmeja tietyn muotoisten lukujen tarkistamiseksi. Suurimmat nykyään tunnetut alkuluvut ovatkin muotoa 2^k-1 eli Mersennen alkulukuja. Tätä kirjoittaessa suurin tunnettu (Mersennen) alkuluku on 2^25,964,951-1, eli noin 10^7,816,230. Vertailun vuoksi maailmankaikkeuden alkeishiukkasten lukumäärä on luokkaa 10^80.

Palkintoja uusien alkulukujen löytämisestä jaetaan lähinnä sen takia että uusien lukujen löytämiseksi tarvitsee useimmiten kehittää uusia algoritmeja. Vaikka tietokoneiden laskuteho kasvaakin 2-kertaiseksi parissa vuodessa, eli exponentiaalisesti, uusille pituuden kertaluokille 10-järjestelmässä päästäisiin vain noin 5 vuoden välein. Kuitenkin pienelläkin algoritmin parannuksella saatetaan päästä useampiakin numeroita suurempien lukujen kimppuun."

-Juppe

Vierailija

Jeps, joskus tuommoisenkin kirjoittanut...taitaa olla vuoden takaista tekstiä kun silloin olin innostunut kryptosta, nyt on sovellettu matikka in.

Alkuluvuilla on oikeasti käyttöäkin. Noita todella isoja alkulukuja ei kauheasti käytetä. Tarkoituksena onkin se että niitä ei löydetä keksimättä jotain uutta, esim algoritmia tai muuta laskentamenetelmää kuten hajautettua laskentaa.

Ns. suuria alkulukuja eli 256 bittisiä ja suurempia käytetäänkin varsinkin kryptografiassa. Julkisten avainten salakirjoitusjärjestelmät perustuvat melkeimpä kaikki joko tekijöihinjaon vaikeuteen tai diskreettiin logaritmiin, molemmissa tarvitaan suuria alkulukuja.

Vierailija
Karza
Mitä ihmeellistä tossa on... mä selvittäisin vaikka 1000000000miljardin luvun alkuluvun. No tiiän että olen käsittänyt jotain väärin, mutta ei voi mitään.

Tarkoittanet että selvittäisit "1000000000miljardin" numeron mittaisen alkuluvun? No tee se ihmeessä niin tienaat kaikki kolme palkintoa jotka aikaisemmin mainitsin.

Ongelmana sinulla olisi tosin se, että numeromuodossa ilman pakkausta tuollainen luku veisi 1000000000 miljardia tavua tilaa. Eli pyöristettynä noin 1000 000 000 teratavua tilaa. Kun yleensä kotikoneissa kovalevyjen koko on noin 0,080 teratavua. Jos et ymmärtänyt minkäkokoisesta luvusta on kyse, niin täällä näet luvun kokonaisuudessaan: http://www.mersenneforum.org/txt/43.txt

Vierailija
Paisa
"Suurten alkulukujen löytäminen on erittäin työlästä. Vieläkään ei tunneta determinististä polynomiaikaista algoritmia jolla voitaisiin varmistaa että joku tietty alkuluku tosiaan on alkuluk-- höpön höpön läpä läpä
-Juppe

Totta puhuen en tiedä yhtään, mistä tässä oli kyse, enkä lukenut kuin ensimmäisen virkkeen, enkä oikeastaan täysin edes tiedä, mikä on algoritmi, mutta nämä eivät meinaa mitään, sillä olen löytänyt keinon tunnistaa alkuluku. Nauttikaa

Alkuluku = x
Keinoni: x/2 (jos osamäärä on kokonaisluku, x on alkuluku)

Ja sitten siihen rumaan käytäntöön. WHERE´S MY MONEY, BITCH!?

salai
Seuraa 
Viestejä7095
Liittynyt17.3.2005
Torchi
Totta puhuen en tiedä yhtään, mistä tässä oli kyse,

Tuo osa tekstistä oli täsmälleen oikein muotoiltu. Loppu oli ilmeisesti todistelua siitä, että alkuosa pitää paikkansa?

Mitä tahansa edellä esitetyistä väitteistä saa epäillä ja ne voidaan muuttaa toisiksi ilman erillistä ilmoitusta. Kirjoittaja pyrkii kuitenkin toimimaan rehellisesti ja noudattamaan voimassa olevia lakeja.

Ding Ding
Seuraa 
Viestejä9031
Liittynyt16.3.2005
Liittynyt
Löysin kaksinumeroisen alkuluvun,
joten saan kait 10 senttiä?

Se annettiin jo sille, joka sen ensin löysi.

Mitä sinä enää 10 sentillä teet, sinullahan on omien sanojesi mukaan jo 15, sen pitäisi riittää.

Vierailija
Torchi
Paisa
"Suurten alkulukujen löytäminen on erittäin työlästä. Vieläkään ei tunneta determinististä polynomiaikaista algoritmia jolla voitaisiin varmistaa että joku tietty alkuluku tosiaan on alkuluk-- höpön höpön läpä läpä
-Juppe

Totta puhuen en tiedä yhtään, mistä tässä oli kyse, enkä lukenut kuin ensimmäisen virkkeen, enkä oikeastaan täysin edes tiedä, mikä on algoritmi, mutta nämä eivät meinaa mitään, sillä olen löytänyt keinon tunnistaa alkuluku. Nauttikaa

Alkuluku = x
Keinoni: x/2 (jos osamäärä on kokonaisluku, x on alkuluku)

Ja sitten siihen rumaan käytäntöön. WHERE´S MY MONEY, BITCH!?

No tuohan ei pidä paikkaansa pätkän vertaa. Jos x/2 on kokonaisluku, niin silloin x EI ole alkuluku.

Triviaali tava selvittää onko joku luku alkuluku on tietenkin koittaa jakaa se neliöjuurellaan ja kaikilla sitä pienemmillä luvuilla. Jos joku näistä luvuista jakaa sen tasan, ei luku ole alkuluku. Ongelmana on se, että näitä lukujä on järjetön määrä. 12,7 miljoonaa bittiä pitkän luvun neliöjuuri on 6,35 miljoonaa bittiä pitkä, siis noin 2 miljoonaa lukua pitkä kymmenjärjestelmässä. Vertailun vuoksi maailmankaikkeudessa on n. 10^80 alkeishiukkasta.

Tietokone pystyy laskemaan kerto ja jakolaskuja noin n^1,61 ajassa jossa n on luvun pituus prosessorin väylän leveyden kertoina. Esimerkkitapauksen 12,7Mb luvulla ja 64b prosessorilla n on siis noin 200000. Prosessorilta menee siis 350 miljoonaa laskuoperaatiota YHDEN tällaisen jakolaskun suorittamiseen. 3,5GHz 64bittiseltä prosessorilta siis 1/10 sekuntia. Ei siis kuitenkaan mikään kauhea aika, vaikeaksi se muuttuu vasta kun tällaisia laskuja tulisi suorittaa 10^2000000 kappaletta. Tällä samalla koneella sen laskeminen kestäisi noin 3*10^199992 vuotta, suhteellisen pitkä aika verrattuna maailmankaikkeuden ikään 1,3*10^9 vuotta...eli 2*10^199985 kertaa kauemmin kuin maailmankaikkeus on ollut olemassa.

Huomattavasti nopeampi algoritmeja on onneksi kehitetty. Algoritmihan on oikeastaan vain joukko sääntöjä joilla edetään tehtävässä. Deterministisyys tarkoittaa että ohjelman suoritus päättyy aina eli se löytää aina oikean ratkaisun. Polynomiaikaisuus tarkoittaa että algoritmi toimii ajassa n^c missä n on sama kuin aikaisemminkin ja c on jokin vakio. Tällaista algoritmia sanotaan myös ratkeavaksi.

Tärkeimmät alkulukutestit ovat probabalistisia, siis ne joko eivät välttämättä toimi oikein tai ne eivät välttämättä anna tulosta. Niissä ideana on se että nämä väärintoimimisen mahdollisuudet saadaan puristettua äärimmäisen pieniksi käyttämällä tarpeeksi laskentatehoa, eli ajamalla algoritmi useaan kertaan käpi.

edit: Tulipa näköjään toistettua aika reippaasti samoja asioita mitä aikaisemmassa tekstinpätkässäni oli, anteeksi siitä. Tosiasia kuitenkin on, että siinä sanottiin suunnilleen kaikki mitä maallikkotasolla asiasta tulisi ymmärtää. Ammattilaiset rupeavat sitten hieromaan niitä algoritmeja.

Vierailija
twoDogs
Torchi

Keinoni: x/2 (jos osamäärä on kokonaisluku, x on alkuluku)



Vai kahdella jaollinen?

No kun Urantia -kirjassa sanottiin näin.

Vierailija
Torchi
twoDogs
Torchi

Keinoni: x/2 (jos osamäärä on kokonaisluku, x on alkuluku)



Vai kahdella jaollinen?

No kun Urantia -kirjassa sanottiin näin.

Parillinen on pikkasen eri asia kuin alkuluku

Vierailija
afastest
Torchi
twoDogs
Torchi

Keinoni: x/2 (jos osamäärä on kokonaisluku, x on alkuluku)



Vai kahdella jaollinen?

No kun Urantia -kirjassa sanottiin näin.

Parillinen on pikkasen eri asia kuin alkuluku

Tai alkuluvun määritelmän mukaan: alkuluku on jaollinen vain 1:llä ja itsellään. Joten parillisista luvuista ainoastaan 2 on alkuluku.

Äärimmäisen ison alkuluvun löytäminen hankaloituu joka kerta, kun siihen asti suurin löydetään. Algoritmilla on etsinnässä merkittävä vaikutus, jotta etsintään saadaan jotain tolkkua. Laskettavaa ja tutkittavaa tulee jokaisen n+1 tapauksessa hillittömästi lisää, kun puhutaan tuon suuruusluokan luvuista (10 000 000 merkkiä). Luku on hillitön, koska luvun miljoona esittämiseen tarvitaan 7 merkkiä.

Uusimmat

Suosituimmat