WEB Security (baziran na prostim brojevima)

[*SNP*]

Pre nekoliko dana sam procitao u jednom od srpskih casopisa, statiju koja nakratko objasnjava tipove sigurnosti i enkripciju elektronske poruke i fajlova. Imalo je mnogo toga (sifriranje poruka, da nebi drugi ljudi lako mogli da razbiju sifru i procitaju poruku), ali kao najglavnije je bila, osnovna baza na kojoj se danasne elektronske poruke sifriraju tj mnozenja odredjenih prostih projeva.

Nekoliko dana sam se mislio i trazio formulu koja omogucava dobijanje svih prostih brojeva (brojevi koji mogu da se podele iskljuciv samim sobom i s brojem 1).
Molim vas ukoliko neko je upoznat ovom problematikom ako moze da mi kaze gde mogu da nadjem odgovor na ovo pitanje i jos neke dodatne (malo detaljnie) informacije o sifriranje fajlova na webu itd.

Izvinite za moj srpski. Ja zivim u Skopju pa nisam dobro upoznat srpskim padezima ali sam inace srbin u dusi. hahahaha

Hvala vam unapred!

[pyost]

Ne postoji formula za tacno pronalazenje prostih brojeva

[*SNP*]

Da znam to ali sam negde procitao da su neki naucnici pronasli formulu ali da ta formula nije vazila za nekih prostih brojeva. Pa sam hteo ako neko zna slucajno tu "formulu" (polivicnu) da mi kaze.

U svakom slucaju hvala na odgovoru.

[KarloBasic]

Preciznije receno, postoji algoritam za nalazenje prostih brojeva, ali ne postoji efikasan algoritam za pronalazenje istih. Posto ja mislim da ih ima beskonacno mnogo( nikad nisam brojao pa nisam siguran ) ne mozes ih sve naci.
Najjednostavniji(najsporiji) algoritam je sledeci:
1. izaberes broj n
2. proveris da li je deljiv sa bilo kojim brojem manjim od sebe osim jedinice.
3. ako jeste onda je slozen, ako nije onda je prost.
4. i tako redom do kraja zivota .

Malo efikasniji nacin je da pamtis proste brojeve u nekoj memoriji (npr niz).
Krenes redom 2,3,5...
1. proveris da li je broj deljiv sa bilo kojim prostim brojem manjim od sebe.
2. ako jeste onda je slozen, a ako nije onda je prost i upises ga u memoriju.
3. i tako redom opet do kraja zivota.

Ovako se dobijaju redom prosti brojevi (2,3,5,7,11,13,17.....)

Za kodiranje se koriste veoma veliki prosti brojevi sa nekoliko stotina decimala. ( Izvor: http://sr.wikipedia.org/sr-el/RSA )

Ako ti treba veliki prost broj mozes da ga nadjes u obliku Mersenovog prostog broja (http://sr.wikipedia.org/sr-el/%D0%9C...B5%D0%B2%D0%B8)
a njega mozes proveriti pomocu Lukas-Lemer test-a (http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test)

U svakom slucaju ovo je veoma "skupa operacija" ( ne mislim na novac, nego na potrosene resurse: memoriju, vreme....) za izvrsavanje na serveru.

Ako ne planiras da cuvas nesto preterano vazno, najbolje je da sam napravis svoj programcic za kodovanje. Mislim da ima nekoliko primera ovde na forumu.

[*SNP*]

Hvala puno. Dao si mi bas to sto sam trazio. Bulls eye! Cuo sam za Mersena, pa me on i zaintrigirao da pronadjem njegov nepotpuni algoritam ali sam mu zaboravio ime.
Hvala jos jedamput.