» »

Odkrito 47. Mersennovo praštevilo

Odkrito 47. Mersennovo praštevilo

Marin Mersenne

vir: Wikipedia
Slashdot - Mersennova praštevila je prvi raziskoval že Evklid, a so dobila ime po francoskemu učenjaku iz 17. stoletja, Marinu Mersennu. Ta je sestavil seznam praštevil - tj. števil, ki imajo samo dva pozitivna delitelja (sebe in enico) - ki se poleg tega dajo zapisati kot 2n - 1. To so Mersennova praštevila, ki jih poznamo le 47. Za lovce na enormna praštevila so pomembna zato, ker zanje obstaja eleganten test, ki z malo surove moči določi, ali je neko število Mersennovo praštevilo. Obstaja celo združenje iskalcev čim večjih praštevil. Matematični navdušenci pa zagotovo poznajo tudi povezavo med Mersennovimi praštevili in popolnimi števili.

Najnovejše Mersennovo praštevilo je odkril Odd Magnar Strindmo iz Norveške. Gre za število 242.643.801 - 1, ki v decimalnem zapisu porabi več kot dvanajst milijonov števk. Zanimivo je, da to ni največje znano Mersennovo praštevilo, saj so že lanskega avgusta pokazali, da je 243.112.609 - 1 tudi praštevilo. Izračun je Norvežanu vzel 29 dni procesorskega časa na trigigaherčnem Intel Core2 in ga je dokončal letos aprila, pred nekaj dnevi pa so v Grenoblu z neodvisnim poskusom potrdili verodostojnost odkritja. Klik!

50 komentarjev

«
1
2

__Devil__ ::

špica ! 8-)

christooss ::

Hm a lahko en pove kako eden sploh za katero številko reče ej to je Marsennovo praštevilo in gre nato preverjat? Al je to for zanka in pač ko eno število ni Marsenovo doda 1 in gre znova preko dokaza?
Zakaj je nebo modro? Da imamo lahko sladoled Modro Nebo

PNG ::

29 dni je potreboval, da je preveril eno število. Najbrž res kar grejo z n+1 zanko preverjat, ja...

jype ::

Najbrž najprej pogledajo tazadn bit in če je 0 ne probavajo :)

PaX_MaN ::

// Determine if Mp = 2p − 1 is prime
Lucas-Lehmer(p)
var s ← 4
var M ← 2p − 1
repeat p − 2 times:
s ← ((s × s) − 2) mod M
if s = 0 return PRIME else return COMPOSITE

For zanka, ja. :P

terryww ::

Me zanima če bo iskanje hitrejše, zdaj, ko je objavljen nov vzorec prašt., ki omogoča napoved prvih nekaj cifer praštevila.

29 dni na Core 2? Kaj na Norveškem pa ne rabijo ECC al kaj...

Zgodovina sprememb…

  • spremenil: terryww ()

MaCoFaCo ::

A se ni tudi Thomas nekaj ukvarjal z napovedovanjem teh števil (oz. njegov program)?

war-dog ::

Nebi bilo boljše kakšne grafične v SLI ali Crossfire dat pa naj grafična melje?
Object reference not set to an instance of an object.

Thomas ::

http://critticall.com/mersenne.html

Tkole se je Thomas ukvarjal. Prepuščam zadevo igranju s Critticall.

jype ::

Thomas> Tkole se je Thomas ukvarjal. Prepuščam zadevo igranju s Critticall.

Jaz upam, da si pobral tudi kakšno od teh nagrad, ker so točno temu (razvoju softvera) namenjene.

Thomas ::

Ne, ne. Nisem se več ukvarjal kot piše na linkani strani. Kakšen dan dela sem že vložil in potem pustil do danes. Mogoče bom kasneje popravil še par slovnično pravopisnih na njej.

tx-z ::

Js rečm da je naslednje število nekje med 248.876.165-1 in 248.896.174-1 :P
tx-z

Zgodovina sprememb…

  • spremenilo: tx-z ()

phantom ::

Hm a lahko en pove kako eden sploh za katero številko reče ej to je Marsennovo praštevilo in gre nato preverjat? Al je to for zanka in pač ko eno število ni Marsenovo doda 1 in gre znova preko dokaza?


Preberi novico. Mersennova števila so števila oblike 2n - 1. Izrek pravi, da če je Mersennovo število praštevilo, potem je tudi n praštevilo. Obratno v splošnem ne velja, je pa relativno velika verjetnost, da velja (v primerjavi z naključno izbranim število enakega velikostnega reda). Torej izbereš si poljubno čim večje praštevilo p in potem greš preverjat če je 2p - 1 praštevilo.
~
~
:wq

Zgodovina sprememb…

  • spremenil: phantom ()

Thomas ::

Zelo malo verjetno je, da je 2p-1 praštevilo. Zelo malo verjetno.

gumby ::

2-1 ne šteje? :D
my brain hurts

Thomas ::

Ni praštevilo. Kar vsako naravno število ga deli.

Dragi ::

V čem je sploh fora da poznamo praštevila? Mislim, kje je korist od tega?

phantom ::

A znaš potem pokazat, da je ∞ deljivo z vsakim naravnim številom?
~
~
:wq

Thomas ::

@phantom

Znam.

@Angel

Koristi začuda so (velike).

jype ::

phantom> A znaš potem pokazat, da je ∞ deljivo z vsakim naravnim številom?

Seveda.

phantom ::

Formalno gledano, deljenje, množenje, seštevanje ipd. z ∞ ni definirano. Pravzaprav ∞ sploh ni število. Zato je o njegovi deljivosti načeloma nima smisla govorit ;)
~
~
:wq

Thomas ::

Nimaš prav. Vsako celo število razen 0, je deljitelj števila neskončno, če si ga že uvedel.

phantom ::

@Thomas
Nimaš prav. Vsako celo število razen 0, je deljitelj števila neskončno, če si ga že uvedel.


Še enkrat preberi moj post, nisem ga uvedel :P.

V splošno uveljavljeni matematiki se ∞ ne vzame kot število niti zanj niso definirane operacije. Seveda lahko rečemo, da ga bomo šteli med števila in definiramo operacije zanj ter pokažemo, da so definicije dobre. Rezultat je precej bizarna struktura, saj z ∞ porušimo strukturo grupe/kolobarja/obsega ipd., posledično tudi običajna računska pravila za kolobarje, obsege ipd. ne veljajo avtomatično (jih moramo posebej dokazati) ali pa sploh ne veljajo.

Ker v tej temi nikjer nismo vpeljali "števila" ∞, tudi z njim ne moremo kar tako operirati.
~
~
:wq

Thomas ::

To ni nobena "bizarna struktura", to je "dopolnjena realna os".

Seveda zgubiš lastnosti kolobarja. Ampak uvedeno število neskončno je lepo deljivo.

"kar tako" pa ne moreš oprirati nikoli.

White&Nerdy ::

Bi lahko to formulo dali na IBM Gene, pa bo blo v nekaj dneh fertik ali cel urah, fertik.:P

jype ::

MoulinRouge> Bi lahko to formulo dali na IBM Gene, pa bo blo v nekaj dneh fertik ali cel urah, fertik.

Žal ne.

boho ::

Kje pa pridejo ta števila v poštev ?

ALT ::

in kaksne so koristi od teh stevil? kaksen konkreten primer ce kdo ve?

pa s cem sploh racunajo ta stevila?

PNG ::

Enkrat sem nekje bral, da se ta števila uporabljajo za enkripcije - nekaj v smislu najmanj možnosti odkritja. Nisem ziher, ker nisem programer.

Števila računajo tako, da delijo število v vprašanju z vsakim predhodnjim številom in vidijo, če obstaja ostanek. Zato to tudi tako dolgo traja, saj so računski procesi enormni.

Thomas ::

> Bi lahko to formulo dali na IBM Gene, pa bo blo v nekaj dneh fertik ali cel urah, fertik.

Prej. V nekaj minutah.

jype ::

Thomas> Prej. V nekaj minutah.

Pri trenutnem peaku v približno 40s, če bi si lahko privoščili celega, če prav razumem njihov PR.

Blinder ::

A ni lazje vprašat Chucka Norrisa, kakšno je naslednje M. št.?:D
99.991% of over-25 population has tried kissing.
If you're one of the 0.009% who hasn't, copy & paste this in your Signature.
Intel i3-12100f gtx 1080 Pismo smo stari v bozjo mater. Recesija generacija

Thomas ::

Včasih jure klone v trenutku. Včasih se izvija mesece. Pa še takrat ko klone, ima neko simpatično navado, da se dela pametnejšega od mene.

Thomas ::

Bo rekel kdo - zakaj pa potem ne iščejo Mersenov raje z Blue Gene? Zato, ker jih morajo sprobat milijone, da najdejo enega. To bi vzelo celo leto preizkušanja na BG, česar si projekt ne more privoščiti. Tako pomemben pa ni.

Iskanje Mersenovih praštevil je podobno računanju števila PI na vse več decimalk. Čedalje bolj brezveze in lahko pokuri VSAK computing ki ga imamo ali bomo kadarkoli imeli. Nenasitna pošast.

ALT ::

in s kirim programckom se to isce?

pa sam za enkripcije se uporablja pol? al je se kaka uporabna aplikacija?

jype ::

Thomas> Včasih jure klone v trenutku.

?

Glede česa pa naj bi se motil v tem primeru?

Thomas ::

@jure

A je še kakšen, ki tega ne ve??? A samo ti?

@ALT

Je povedano mau višje gor, s kakšnim, by PaxMan. Iteracijsko množenje pravzaprav.

jype ::

Kljub temu me zanima.

Matevžk ::

@jure
A je še kakšen, ki tega ne ve??? A samo ti?

Jaz.
lp, Matevžk

Thomas ::

jype :: včeraj, 20:28:26

MoulinRouge> Bi lahko to formulo dali na IBM Gene, pa bo blo v nekaj dneh fertik ali cel urah, fertik.

Žal ne.


A si pozabu al kaj?

Danes ko sem jaz MoulinuRouge-u vlil upanje, si se pa hitro strinjal.

Kakšnega jokerja izigravaš?

Matevžek tud ne zna brat?

Zgodovina sprememb…

  • spremenil: Thomas ()

jype ::

Am.

"Žal ne" leti na dejstvo, da sodobna kriptografija (ki se trenutno uporablja) temelji na velikih številih, ki jih sodobni računalniki zmeljejo prej kot v "nekaj urah".

K sreči je to še vedno predrago za gledat moj slo-tech promet, ni pa niti približno nemogoče.

Saj pri IBM so dost glasni o tem kaj mašina zmore, pa mislu sem, da je vsakemu jasno, da mora samo delit število potrebnih operacij z OPS od mašine, pa dobi sekunde.

Thomas ::

Kaj si "mislil da je vsakemu jasno", je eno. Kaj si pa napisal, je pa drugo.

V tem primeru nekaj nasprotnega.

jype ::

MoulinRouge> Bi lahko to formulo dali na IBM Gene, pa bo blo v nekaj dneh fertik ali cel urah, fertik.
jype> Žal ne. (Fertik bi bilo v nekaj deset sekundah.)

A tko bi moral napisat, da bi bilo tudi tebi jasno?

Thomas ::

Meni so stvari jasne, s tvojimi komentarji ali brez.

Hvala.

PNG ::

jype, zakaj se vlečeš ven? Zajebal si, kaj češ.

Če ne bi mislil obratno, ne bi napisal ŽAL, ker jaz ne vidim nobenega razloga zakaj bi bilo to slabo.

jype ::

i100k100> ker jaz ne vidim nobenega razloga zakaj bi bilo to slabo.

Huh?

Pet let nazaj smo bili prepričani, da so 128bitni ključi dovolj dobri za zares zasebno SSL sejo, danes pa vemo, da obstajajo javno dostopni (torej, na tržišču dostopni) računalniki, ki zmorejo lomit ključe v _realnem času_.

PNG ::

Aha, torej je odkrivanje praštevil slabo dejanje, po tvojem mnenju.

Okej.

PNG ::

Aja, samo to še, kako slabo je to dejanje? V kateri krog pekla po Danteju se uvrstiš, če odkriješ veliko praštevilo?

Hvala

techfreak :) ::

Aja, samo to še, kako slabo je to dejanje? V kateri krog pekla po Danteju se uvrstiš, če odkriješ veliko praštevilo?

Hvala

9. krog
«
1
2


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Znano novo največje praštevilo

Oddelek: Novice / Znanost in tehnologija
268128 (5264) win64
»

Odkrili največje doslej znano praštevilo

Oddelek: Novice / Znanost in tehnologija
136490 (5133) reeves
»

Odkrito novo največje praštevilo

Oddelek: Novice / Znanost in tehnologija
238174 (5063) marko181914
»

Odkrili novo največje praštevilo

Oddelek: Novice / Znanost in tehnologija
108266 (5189) PaX_MaN
»

Najverjetneje odkrito štirideseto Mersennovo praštevilo

Oddelek: Novice / Znanost in tehnologija
93054 (3054) Thomas

Več podobnih tem