Kako so ugotovili, da je 2^13466917-1 praštevilo.

......jebo ga.....ko bi jst kaj kapiral kaj ti pišeš :) ....

Nic jasno...

rc-car

Prvi postopek se konča s celim številom (2) - zato je 31 praštevilo.

Drugi postopek se neha "z decimalkami", zato 63 ni praštevilo.

Je pa postopek uparaben zgolj za števila oblike 2^N-1.

IceMan

Samo na tem forumu.

Ja Lucas pa Lehmer sta se ga zmislila ane.

Drugače je pa tko, da če bi hoteli s standardnim algoritmom (deljenjem z vsemi praštevili manjšimi od korena) to reč preizkusiti ...

... bi lahko pretvorili vsak atom vesolja - v novo vesolje - tako ene tisočkrat - potem pa iz vsega naredili superračunalnik - pa ne bi bil fertik v gugol letih. Niti še dobro ne bi začel.

Kje se pa da dobit ta prog, da potem ti rac to racuna? Sej je tko kot seti?

Enkrat si moram cas uzet in se poglobit v to enacbo, ker se mi zdele ne da

Ej Thomas, a z erastatenovim rešetom al kak se mu že reče se to ne da?

Ni kaj.

Vendar ali mi lahko kdo bolj natančno razloži kaj pridobimo z tako velikimi praštevili in če mi lahko napiše praktičen primer.

IN kakšna je že povezljivost praštevila - prafaktorji??


LP

Samo starejsi sifrirni algoritmi se delujejo s pomocjo izbiranja prastevil.

Thoma: Hvala lepa. S tem si me potolažil. Nikakor si nisem mogel predstavljati, čemu bi bila tako velika praštevila namenjena. Torej z razlogom si nisem mogel predstavljati.

Prafaktorji in praštevila.

Na hitro pobrskal.
Če število 1683 raztavimo na produkt praštevil dobimo 1683=2*3^2*7*13
Števila ki nastopajo večkrat pri tem produktu imenujemo prafaktorji. V tem primeru je število 3 prafaktor.

LP

Avenger

Če bi spraševal o Area 51 - bi se res pomilovalno nasmehnil. V tem primeru pa nikakor.

Point je pa v tem, da nekatere to grozno zanima. Kaj imajo pa tisti od tega, ki jih to nič ne zanima?

Zaenkrat nič. Kdo ve, če sploh kdaj kaj. Vendar je vsako znanstveno raziskovanje tako. Mogoče ne bo iz zadeve nič (splošno uporabnega) - morda pa le bo.

Kar se praštevil tiče - ampak ne (samo) Mersennovih - imajo zgleda eno aplikacijo na DNA.

To se pa gotovo tiče vsakega izmed nas.

Zile

Mersenova (pra)števila so podmnožica (pra)števil. Okay?

In tip ni kasiral nič, ker je nagrada razpisana za 10 milijonov DECIMALNIH mest.

A kdo od vas kej ve, kje na netu naj bi se nahajali algoritmi, ki recimo iscejo prastevila? Dolgo tega sm naredil program, ki jih isce, pa bi ga rad malo optimiziral.

Doppelganger

[dobr nick, mladi mož]

Tle gor vrž svoj algoritem, ti ga bom mal skritiziral. Konstruktivno.


Brane2

Težko deljivih števil v šifriranju ne uporabljajo (profiji) več - iz nekega na prvi pogled sila nenavadnega razloga.

Prav možno je, da bodo kvantni računalniki realnost v parih letih. Potem bo mogoče zelo hitro sfaktorizirati "vsako" število - in kompromitirat vsa par let stara sporočila.

Če koga zanima - bom jutri razložil algoritem, po katerem bodo deljitelje iskali kvantni računalniki.

Tudi mene ne zanima iz drugega razloga kot firbca...
No ja, mogoce bom enkrat dal na eni 486ki tak algoritem laufat kak mesec, da vidimo rezultate

Thomas:

Brane2

>Težko deljivih števil v šifriranju ne uporabljajo
>(profiji) več - iz nekega na prvi pogled sila >nenavadnega razloga.

Res ? Zakaj pa je glih faktorizacija števil tako ranljiva na kvantne mašine in ne recimo kaj drugega ?

Na tem področju sem slab, a vsaj tisto malo, kar sem o razvoju teh mašin zasledil skozi Net mi ne daje jasen odgovor na to vprašanje.

Kokr vidim, QM so/bodo mojstri za delo z verjetnostmi, oziroma različnimi možnostmi naenkrat v enem "Qbitu". Algoritmi, ki niso predvidevali razvoja QM so lahko ranljivi, tisti pa ,ki so prilagojeni temu, izkoriščajo slabosti teh pristopov, recimo zahtevajo ogromno Qbitov in nenormalne natančnosti...

Prav možno je, da bodo kvantni računalniki realnost v parih letih. Potem bo mogoče zelo hitro sfaktorizirati "vsako" število - in kompromitirat vsa
par let stara sporočila.

Ne vem, kok si star, ampak jaz sem poslušu te fore od otroštva:

- čiperaj na Si nikol ne bo pršu čez 500MHz zaradi fundamentalnih meja, kot je recimo mobilnost elektronov v Si...

-prvi optični računalniki so že narejeni, serijska proizvodnja je vprašanje časa...

- projekcije, ki se je pojavla v Mojem Mikru (IIRC), da bodo leta 2000 imeli računalniki celih 100 Mb RAma in 1 Gb diska- kdo bi rabu kej tacga ? Kdo bo napisu tako strojno kodo, da bi šla v tak RAM ? Eh, bli so to časi, ko sem komajda zbral čas za Sinclairjev QL...



>Če koga zanima - bom jutri razložil algoritem, po >katerem bodo deljitelje iskali kvantni računalniki.

Mene zanima. In-depth, please...

Kogar indeep zanima, kako se dela kvantna faktoriziranje, naj pogleda sem:

V enajstih korakih je razložen algoritem, ki ga lahko izvede le tandem kvantnega in klasičnega računalnika. V delčku sekunde lahko ta par faktorizira število, ki bi zaposlilo superračunalnik gugol let.

Jest bom poskusil razumljivo pojasniti, v čem je bistvo.


Da se narediti mnogo raznoraznih molekul. Recimo da nam predstavljajo različna števila od 0 do 2^milijardo. Rečemo, da jih determinira milijardo qbitov.

Da se narediti taka molekula, ki prereže vsako teh molekul na dve takšni molekuli, ki predstavljata dve števili, katerih produkt je prva molekula.

To je quantum factorization.

V resnici pa potrebujemo eno samo molekulo, v toliko različnih stanjih. Operacija na njej (laserski impulz naprimer) jo spremeni v molekulo, ki je njen največji delitel.

V resnici ne potrebujemo niti molekule. Oblak elektronov lahko počne isto. Oblak elektronov je kvantni register, kjer so 0 in 1 in superpozicije 0 in 1. Obe - 0 in 1 hkrati, dokler proces ne poteče.

Subatomski svet, kot bi nam hotel nekaj informacije prikriti. Toda ravno to potem lahko izkoristimo za hkratno procesiranje vseh stanj, ki so možna.

V makro svetu razbijemo cegu in število atomov v njem razdelimo na vsoto dveh. Trivialna operacija - nati dve števili, katerih vsota je znano število.

Za produkt pa ni trivialno najti faktorjev. Toda v subatomskem svetu obstaja tak mehanizem. Neko kvantno stanje lahko razbijemo na dve stanji, katerih produkt je prvotno stanje.

Simpl - ane?

Thomas:

Nice link, dojel 50%, ostalo poberem v naslednjem preletu.

Bi pa dodal še tole.



Če je kdo bral avtoštoparski vodič po galaksiji, bo pri tej temi našel velik čudno znanih stvari...

Vse skupaj sem zasledil kar nekaj let nazaj. Blo je objavljeno kot da je RSA mrtev, takoj ko pride ven prvi kvantni stroj, ta bo pa takoj tle, sam da gre določen tip, ki je napisu članek srat, praktično takoj bo za pokazat prototip.

Nakar je blo za prebrat par drobnih, majčkenih, nepomembnih in tivialnih zaprek, ki jih bo treba premagat:

-kvantne mašine ne prenesejo temperatur nad absolutno 0. Nikakršnih. Izračunana kvantna stanja zaradi vibracij atomskih mrež izpuhtijo...
Ni zadosti približna 0, rabiš absolutno...

-Register, kjer imaš Qbit, mora biti totalno nedostopen celotnemu vesolju cel čas, ko hrani rezultat in povsem dostopen, ko ga je treba prebrati ali vpisati.

-nikoli ne veš, kaj je v registru, dokler ga ne pogledaš. Ko si enkrat pogledal, njegovo stanje izmed vseh možnih variant kolabira v neko konkretno z neko verjetnostjo. Baje nikoli ne moreš bit prepričan, če si prebral tapravo stvar in je treba delat z verjetnostjo.

-tud dosedanji Qbiti so zgledal čudno. Eden je recimo zasedal četrt inštituta, saj so kot qubit uporabli svetlobni kvant, ujet v mikrovalovno luknjo v vakumu.
Jasno, vse to dobiš u Konradu...

Po junaških naporih in obilnem nažiganju (tega ni mogu smislit trezen) je pršu nek mladi japonski matematik do tega, da bi se recimo tud šalca vroče kave lahko obnašala kot Qbit, ki bi lahko dihtala informacijo zadosti dolgo za uporabno delo.
Za to je ponucal valovne funkcije, statistične trike in bogve kok kave...

U glavnem, ni blo opazit, da bi Nescaffe neki nepojasnjeno poveču prodajo, torej bo mogoče treba še mal počakat...



Hočem, reč, če ne bo kakih resnih tehnoloških shortcutov, bo še kar nekaj časa glavna stranka NSA, ki lahko ponuca za Qbite tud jajca polarnega komarja, če je treba, mi bomo pa uporabljal bolj varno enkripcijo in to je IMHO vse.

Jaz bom pa med tem časom obudil Šponarco (Vegova rulez )od mrtvih
in naredu major update/patch/upgrade na svoji matematki...

BTW: Ena (kao)koristna aplikacija tega je že v vojaških sistemih, kjer prenašajo podatke po vlaknu.
Če uporabljaš monomodno steklo, lahko celoten fiber od mašine A do mašine B uporabiš kot nekakšen Qbit.
Ker register zavzame konkretno vrednost šele ko ga opaziš (kje jemljejo te fore ? Iz risank ?) bi vsak vsiljivec povzročil spremembo v fibru...

Thomas:

>S qbiti se bo treba kmalu navadit delat, še bolj >verjetni pa so kvantni kompajlerji, ki bodo navadno >Turingovo kodo avtomatično prevedli v >transTuringovo qcodo.

Tole zveni kot reklamni slogan, ki bi si ga prvšču kak Intel.

"Mogoče ste mislili, da so naši čipi sranje, a ni res. Samo niste uporabili tapravega compilerja.
Rabte taprave optimizacije za naš rapid-execution-multiflow-son-of-a-bitch engine..."

Turing to non-Turing ? Zveni simple. Približno tko kot iz Slovenščine v Forth...

Hočem reč, to je teorija. Daleč je še do komunizma...

Glede na to, kolk qbitov bojo verjetno mele prve mašine, mislim da je poštena primerjava z recimo današnjimi najmanjšimi 8-bitnimi mikrokontrolerji.
Tam se pa ve, če je prostor dragocen, je asembler majka.
In pri teh strojih bo prostor RES dragocen...

Če bi folk zvedu, da si kodo šu programirat v C-ju ali nedaj bože v QVisual Basicu in so zarad tebe moral kupit 128 M QRAMa po kilodolar za bit-jao...

Zakaj se folk zmeri obeša na zgrešene predikcije, ne da bi omenjal tudi pravilno (v nekih mejah, jasno) napovedane stvari ?

Nč nisem zabetoniral. Samo pravim, da tole ne bo glih "jutri" in da se bomo do takrat še nagledal čudes.

ne vidim, kako bo evolutivni razvoj v nekem doglednem času pripeljal do tega...
Mislim, da bo potrebnih vsaj nekaj "kvantnih preskokov" in nepričakovanih razvojev, da bomo to v znatni meri videli v kratkem (recimo, 5-10 letih).

Poglej si, recimo navadne, trapaste LED-ice. Obstajajo IIRC že 40 let, ampak šele zadnjih kok, 6-7 let razturajo in to po zaslugi tipov v HPju, Siemensu in predvsem NIchia-i, kjer gre zasluga za to poleg norim tehnologom vsekakor tudi fizikom.

Šele zdaj se LEDica sploh omenja kot resna (ejša) konkurenca žarnici, če pogledaš brainwork za tem razvojem in prehojeno pot, te srat prime...

Tu na začetkih LEDic je folk sanju o tem, kako bodo zamenjale lampe, a kot je znani filozof 21-tega stoletja reku:

"Walking the path isn't the same as knowing the path, Neo.."--MATRIX

Thomas:

>Vse priznanje vsem, ki so v tem sodelovali. Predvsem Nakamuri iz >Nichie, ki je eden - brez pretiravanja - najbriljantnejših >raziskovalcev v zgodovini človeštva.

Ja, tip je baje raztural v Nichii, kjer vladajo KOMUNISTIČNI pogoji (mizerna plača, šef mu je stalno sral, vojaška hierarhija, itd.), zato je IIRC šel na Ameriško univerzo raziskovat.
Ni si upal v privat firmo, recimo HP, da ga ne bi pršle iskat triade...

>Toda tedenska simulacija LEDic znotraj Sky Blue - whatever - v >nekaj letih (5 do 10) - bo pomenila več kot 100 let peš ukvarjanja >z njimi...

Lepo si skril unih 5-10 let v oklepaj...
Če bo stvar obstajala v tem času, temu ni treba oporekat...

Sicer pa, tokrat bi se RES rad motu...

Priloga delu, Znanost 9.september, stran 8.

Odmevno odkritje treh indijskih znanstvenikov!
Problem praštevil končno rešen.

En tak simpel algoritem, ki hitro preračuna za ogromna števila, če so praštevila ali ne.
Dejte prebrat!

ehhe komaj sem se prebil skoz thomasove in branetove poste :)
sicer pa moj hp40g ob vnosu 2^13466917-1 izpljune samo en bogi 9.999999999999E499

Algoritem in dokaz pravilnosti algoritma za preverjanje prastevila:
(na temo "Odmevno odkritje treh indijskih znanstvenikov"
http://www.cse.iitk.ac.in/news/primalit...

Treba je samo ločiti med ugotovitvijo, da je neko število sestavljeno - in med njegovo dejansko faktorizacijo.

Ta drugi oreh je pa še naprej trd. Obstajajo števila, za katere vemo da so deljiva. Toda se nam ne sanja, kateri so njihovi deljitelji.

S tem algoritmom, bo takih še več.

Hehe, a bi kdo miljon dolarjev?

Riemann hypothesis

jest sm naredu najbolj enostavn algoritm in stestiru do 1000000 in sm komi pršu do ke

procedure TForm1.FormActivate(Sender: TObject);
var i,j,status,k:integer;
begin
status:=0;
k:=1;
for i:=3 to 100000 do
begin
for j:=2 to (i-1) do
begin
if i mod j = 0 then
begin
status:=0;
break;
end
else status:=1;
end;
if status=1 then
begin
Form1.Memo1.Lines.Add(IntToStr(k)+' ... '+IntToStr(i));
k:=k+1;
end;
end;
end;

zgleda da je treba napisat kej boljšga :)) anyone?