Prosti brojevi

[Trok1^^]

Ljudi kako mogu da dokazem da je neki broj prost? Znam da su prosti brojevi oni koji su deljivi samo sa 1 i sa samim sobom, ali kako npr da dokazem da je broj 19990049 deljiv samo sa 1 i sa samim sobom, odnosno da je prost?!

 

[pura moca]

http://primes.utm.edu/prove/

 

[Trok1^^]

Moze l' na srpskom xD?

 

[Paganko]

Ne verujem da ima na netu... Možda u nekom udžbeniku. Mada, koji će ti to đavo...

Evo ovo je prost broj:

3*2[sup]6090515[/sup]-1

 

[. . .]

Ljudi kako mogu da dokazem da je neki broj prost? Znam da su prosti brojevi oni koji su deljivi samo sa 1 i sa samim sobom, ali kako npr da dokazem da je broj 19990049 deljiv samo sa 1 i sa samim sobom, odnosno da je prost?!

Jednostavno, sednes za komp i napises program koji proverava da li je tvoj broj deljiv sa bilo kojim brojem od 2 do korena iz tog broja i ako nije deljiv ni sa jednim onda je prost, a ako je deljiv bar sa jednom slozen. Formula za nalazenje prostih brojeva ne postoji, a i da postoji ne verujem da bi je mogao naci bilo gde jer se ti prevelike pare muvaju

 

[MathPhysics]

Da li je broj prost trivijalno je proveriti programskim alogoritmima, i to je više zadatak za tu sferu delatnosti, bar kada je praktično izračunavanje u pitanju.

Da broj nije prost ponekad je lako dokazati uočavanjem nekog njegovog delioca različitog od tog broja i jedinice. Očigledno, svi parni brojevi veći od dva su složeni brojevi. Tako da recimo broj 2355692 nije prost. Slično za broj 1212124281 možeš zaklučiti da je složen, jer mu je zbir cifara deljiv sa tri, pa je i on sam deljiv sa tri.

Naravno, to retko prolazi. A dokaz da je dati broj prost, pogotovu ako je u pitanju veći postaje ne tako lakim zadatkom.

Za određivanje prostih brojeva koristi se Eratostenovo sito. Ipak za veće brojeve to je nepraktično, a njih ima beskonačno mnogo (što je pokazao još Euklid). Naravno, ti brojevi nisu tako česti i što veće brojeve posmatramo, sve ih je manje. Postoji tzv. asimptotski zakon raspodele prostih brojeva kojim se opisuje učestalost pojavljivaja prostih brojeva među prirodnim.

Svaki broj se može prikazati kao kanonska faktorizacija pomoću prostih brojeva. Ukoliko u njoj figuriše sam taj broj, onda je dati broj prost.

Ima tu mnogo šta da se kaže, ali šta god kažem, ostaću nedorečen. U suštini ako hoćeš potpun odgovor moraš ga potražiti u ozbiljnijim knjigama, jer ga je teško sročiti kratko. Postoji veliki broj metoda za određivanje toga da li je broj prost ili složen. Recimo Vilsonova teorema kaže da je broj p prost ako i samo ako je delilac (p-1)!+1.Imaš gomilu algoritamskih pristupa i onih koji se baziraju na verovatnoći, ali sve je to više za progamere nego matematičare. Tako imaš proveru Miler-Rabina, test Pepina, AKS test...

 

[Insect]

Hmm, oprostite jednom nematematicaru, ali sto je to toliki problem? Zar nije dovoljan dokaz uraditi deljenje pomocu kopma nekog broja sa svim brojevima pre njega? Bez obzira koliko je veliki broj komp bi to trebalo da uradi za delic sekunde, eventualno par sekundi. I zar ne postoje negde vec spiskovi prostih brojeva do tamo neke n-te velike vrednosti?

 

[Paganko]

Hmm, oprostite jednom nematematicaru, ali sto je to toliki problem? Zar nije dovoljan dokaz uraditi deljenje pomocu kopma nekog broja sa svim brojevima pre njega? Bez obzira koliko je veliki broj komp bi to trebalo da uradi za delic sekunde, eventualno par sekundi. I zar ne postoje negde vec spiskovi prostih brojeva do tamo neke n-te velike vrednosti?

Pa nije neki problem dok ne dođeš do broja sa par stotina cifara...

 

[MathPhysics]

Hmm, oprostite jednom nematematicaru, ali sto je to toliki problem? Zar nije dovoljan dokaz uraditi deljenje pomocu kopma nekog broja sa svim brojevima pre njega?

Da, to prolazi. Šta više, može se znatno uprostiti, jer ne moraš deliti čak ni sa svim brojevima do n kada ispituješ da li je broj prost, već sve brojeve do [\sqrt{n}]. Oznaka [] ovde označava funkciju celog dela, jer \sqrt{n} ni za jedno n iz skupa prostih brojeva nije prirodan broj (da nije tako broj n bi bio deljiv sa svojim korenom koji je prirodan broj, otuda bi bio složen). Naravno ne moramo deliti ni sa parnim brojevima jer znamo da ako je n>2 prost u svojoj kanonskoj faktorizaciji ne sadrži broj dva. Zapravo, dovoljno je ispitati deljivost broja n sa svim prostim brojevima manjim od datog. To bi bio jedan pristup koji bi za manje brojeve koristio i bez računara.

Međutim i kod klasičnog računjanja i kod programskog problem se javlja kod velikih brojeva. Drugi to rešava brzo, i za neke veće brojeve, poput onog iz prve poruke u temi. Ali kod većih brojeva, ali mnogo većih od tog, proces se znatno produžava, čak i uz pomoć računara. Zato postoje programski i matematički pristupi (kao i kombinacije prethodna dva) koji to uprošćavaju. Ja sam naveo neke u prethodnoj poruci.

I zar ne postoje negde vec spiskovi prostih brojeva do tamo neke n-te velike vrednosti?

Postoje. Ali ni izbliza svi prosti brojevi nisu otkriveni (to i ne mogu da budu jer ih ima beskonačno mnogo). Postoji mnogo aktuelnih nerešenih problema u vezi sa prostim brojevima, a jedan od njih koji se uvek rešava je traženje najvećeg do sada poznatog. Inače, uglavnom ih nalaze među Mersenovim brojevima.

 

[MathPhysics]

Ljudi kako mogu da dokazem da je neki broj prost? Znam da su prosti brojevi oni koji su deljivi samo sa 1 i sa samim sobom, ali kako npr da dokazem da je broj 19990049 deljiv samo sa 1 i sa samim sobom, odnosno da je prost?!

Broj 19990049 kongruentan je 17 po modulu 24. To znači da je jedinici kongruentan kvadrat tog broja. Ako je taj broj p sledi da će broj p^2 - 1 biti deljiv sa 24.

Ako je broj p prost onda je p^2 - 1 deljivo sa 24 (dokazuje se kongruencijama po modulu 8 i 3, uz uslov da je p>3). Tako bismo mogli pokazati da broj nije prost, jer bi dobili da ne važi deljivost. Ipak iz ovog mi ne možemo zaključiti da je p prost jer se radi o implikaciji i ne možemo ići u povratnom smeru, ali je jako korisna dosetka koja bi poslužila da se dokaže da broj nije prost (dakle ono što sam napisao je potreban uslov da broj bude prost, ali ne i dovoljan.

Inače, svi prosti brojevi veći od tri se mogu predstaviti u nekom od ova dva oblika: 6k+1, 6k-1. Ovaj iz tvog primera je oblika 6k-1. Ukoliko nijedan od brojeva p-1 i p+1 nije deljiv sa 6, gde je p>3 broj p nije prost (sledi iz prethodno pomenutog tvrđenja). Tako bi takođe mogao za neki broj da pokažeš da nije prost.

A da je broj zaista prost možeš pokušati da dokažeš sa već pomenutom Vilsonovom teoremom. Ako je p prost, onda je p | (p-1)!+1. Naime, za broj p=19990049, (p-1)!=19990048!, što je ekvivalentno 19990048 * 1999047 * 19990047 ... *2*1 možeš članove u proizvodu 19990047 * 19990046 * ... 2 * 1 da grupišeš po dva tako da im proizvod po modulu 19990049 bude kongruentan jedinici. Broj 19990048 je kongruentan -1 po tom istom modulu pa je broj (p-1)! kongruentan -1 po modulu p, što znači da je (p-1)! +1 kongruentno 0 po modulu p što je ekvivalentno uslovu da broj (p-1)!+1 pri deljenju sa p daje ostatak nula, što daje da važi p | (p-1)!+1, zbog čega po Vilsonovoj teoremi broj p=19990049 mora biti prost.

 

[Baraba na kvadrat]

Ma mala fermaova, kongruencija i malo matematcki indukcije i na konju si .... ako mene pitate

 

[MathPhysics]

Ma mala fermaova, kongruencija i malo matematcki indukcije i na konju si .... ako mene pitate

I da i ne.
a[SUP]p-1[/SUP] kongruentno 1 (mod p), tj. malu Fermaovu teoremu, ponekad zadovoljavaju i brojevi koji nisu prosti.

 

[Peruzzi]

bitna tema za kriptografiju, nimalo jednostavan problem.
postoje tablice, tj. spisak, i to za prilicno velike brojeve. pitanje je gde se moze naci, doduse, ali s obzirom na velicinu vrlo je moguce da je do odredjene velicine jeftinije proveravati u hodu nego preko tablice

receno je da postoje potpuni i dokazi zasnovani na verovatnoci. ovi drugi su pouzdani sa odredjenom verovatnocom greske (mada dosta/proizvoljno malom)

ovi prvi su racunski zahtevni i traze dosta vremena ili prostora, pa se u praksi koriste ovi drugi.

a na pitanje - pa postoje superracunari, ajde njih da uposlimo - odgovor je - super, ali proste brojeve koristim za sifrovanje, i trebaju mi u onoj velicini u kojoj superracunar dekriptera nece moci brzo i jeftino da sracuna
brzo znaci = bar 30 godina sa mogucim budzetom
a ne zaboravi na amdalov zakon i napredak tehnologije uopste

 

[Paganko]

http://www.primegrid.com/

 

[Paganko]

65516468355·2[sup]333333[/sup]+1 ili decimalno:

LINK

 

[Paganko]

Zanimljivo je da je i ovaj takođe prost:

65516468355·2[sup]333333[/sup]-1 ili decimalno:

LINK

 

[Insect]

bitna tema za kriptografiju, nimalo jednostavan problem.
postoje tablice, tj. spisak, i to za prilicno velike brojeve. pitanje je gde se moze naci, doduse, ali s obzirom na velicinu vrlo je moguce da je do odredjene velicine jeftinije proveravati u hodu nego preko tablice

receno je da postoje potpuni i dokazi zasnovani na verovatnoci. ovi drugi su pouzdani sa odredjenom verovatnocom greske (mada dosta/proizvoljno malom)

ovi prvi su racunski zahtevni i traze dosta vremena ili prostora, pa se u praksi koriste ovi drugi.

a na pitanje - pa postoje superracunari, ajde njih da uposlimo - odgovor je - super, ali proste brojeve koristim za sifrovanje, i trebaju mi u onoj velicini u kojoj superracunar dekriptera nece moci brzo i jeftino da sracuna
brzo znaci = bar 30 godina sa mogucim budzetom
a ne zaboravi na amdalov zakon i napredak tehnologije uopste

Hoces da kazes da imaju brojevi (upotrebljivi brojevi) za koje racunar ne moze da uradi sve operacije deljenja za manje od 30 godina?! O.o A koliko ce vremena trebati jednom kripteru da ubaci (otkuca) taj broj u svoju tajnu poruku ?

 

[MathPhysics]

Hoces da kazes da imaju brojevi (upotrebljivi brojevi) za koje racunar ne moze da uradi sve operacije deljenja za manje od 30 godina?!

Ne znam sta podrazumevas pod "upotrebljiv broj", ali jasno da postoji beskonacno mnogo prirodnih brojeva, kao i da proces kontinuiranog deljenja moze da traje i duze od toga kod jako velikih brojeva.

 

[. . .]

Hoces da kazes da imaju brojevi (upotrebljivi brojevi) za koje racunar ne moze da uradi sve operacije deljenja za manje od 30 godina?! O.o A koliko ce vremena trebati jednom kripteru da ubaci (otkuca) taj broj u svoju tajnu poruku ?

Gledaj na sve to vise ovako, recimo da najbrzem mogucem racunaru za broj od 20 cifara treba jedan sekund da utvrdi da li prost ili ne, Znaci za broj od 40 cifara trebace mu 2 sek. za jedan minut on moze da ispita broj od 20*60=1200 cifara, za jedan sat 1200*60 = 72000 cifara za ceo dan 72000*24, za godinu pomnozi taj broj sa 365 i za 30 godina sa jos 30 i onda izaberi jedan broj sa tim krsem cifara i stavi u komp pa za 30 god. proveri da li prost ili ne. Ali da budemo sigurni da ce komp da radi i za 30 godina tu uzmi dva puta toliko cifara koliko si planirao. Takav broj definitivno postoji a sad da li ces za zivota videti da li je prost ili ne, to je vec tvoj problem A pri tome ne zaboravi da je sasvim moguce da ima neki tako velik broj da se izgubis i dok kazes koliko ima cifara a da se zna sa manjom ili vecom verovatnocom da li je pouzdan ili ne

 

[Paganko]

Gledaj na sve to vise ovako, recimo da najbrzem mogucem racunaru za broj od 20 cifara treba jedan sekund da utvrdi da li prost ili ne, Znaci za broj od 40 cifara trebace mu 2 sek. za jedan minut on moze da ispita broj od 20*60=1200 cifara, za jedan sat 1200*60 = 72000 cifara za ceo dan 72000*24, za godinu pomnozi taj broj sa 365 i za 30 godina sa jos 30 i onda izaberi jedan broj sa tim krsem cifara i stavi u komp pa za 30 god. proveri da li prost ili ne. Ali da budemo sigurni da ce komp da radi i za 30 godina tu uzmi dva puta toliko cifara koliko si planirao. Takav broj definitivno postoji a sad da li ces za zivota videti da li je prost ili ne, to je vec tvoj problem A pri tome ne zaboravi da je sasvim moguce da ima neki tako velik broj da se izgubis i dok kazes koliko ima cifara a da se zna sa manjom ili vecom verovatnocom da li je pouzdan ili ne

zato postoji mreža za distribuirano računanje u okviru BONIC projekta koja se bavi potragom za prostim brojevima:

http://www.primegrid.com/

u suštini, skinete BONIC sa neta, prikačite projekat primegrid i to je to. U slobodno vreme, procesor se koristi za tu svrhu... Bila je i tema:

http://forum.krstarica.com/showthread.php/353843-Berkeley-Open-Infrastructure-for-Network-Computing

 

[Peruzzi]

da pomenem - pricamo u dekadnom sistemu. u binarnom je to sve malo duze

termin 'upotrebljiv broj' je prilicno dobar, zapamticu ga. kad sam pomenuo 30 godina - radi se o sledecem: ako sifrujes poruku nekim kljucem koji biras iz skupa od, npr. 30 clanova (a-š), onda je vreme potrebno da se sifra razbije brute force-om = 30 x vreme desifrovanja poruke. Za n mogucih kljuceva = n x vreme des.

posto je vreme desifrovanja konstantno, u proceni slozenosti moze da se zanemari, pa je slozenost brute-force napada reda n.
uzevsi u obzir trenutno stanje tehnike, i procene za 30 godina, da se, uz malo muke, izracunati koliko n treba da bude veliko tako da do 2042 brute-force napad nece biti izvodiv za manje od x novca ulaganja

ovde smo pretpostavili da je algoritam neunistiv na drugi nacin sto nije uvek slucaj (rsa - diskretni logaritam)

ostaje otvoreno pitanje novca.

svaka informacija kosta.
evo ovako - imam program cija izrada je kostala 10.000 evra i bice aktuelan narednih 10 godina (posle ce vreme da ga pregazi). i sifrujem ga. dovoljno je da desifrovanje zahteva bar 10 godina (jer tad i ako desifruje briga me-program je ionako zastareo) ili bar 10.000 evra troska (jer ako je voljan da da 10.000 evra, pre ce da ga kupi ili sam napravi, nego da razbija i rizikuje pravne zajbancije)