|
01. 02. 2006. | #1 | |
Dejan Katašić
Wrote a book
Datum učlanjenja: 10.06.2005
Lokacija: Novi Sad
Poruke: 1.017
Hvala: 129
86 "Hvala" u 43 poruka
|
Citat:
|
|
15. 02. 2006. | #2 |
Branimir Momcilovic
Qualified
Datum učlanjenja: 15.02.2006
Lokacija: Beograd
Poruke: 167
Hvala: 47
25 "Hvala" u 8 poruka
|
ciklicna grupa
Nisam citao celu diskusiju tako da se unapred izvinjavam ako je neko vec dao ovu ideju.
Problem se svodi na teoriju brojeva, dakle ciklicna grupa i njen generator. npr. trebaju mi sve cifre (0-9) oznacicu skup za Z10, teorija kaze da ako uzmem bilo koji broj, zvacemo ga g, koji je uzajamno prost sa 10, on je generator grupe Z10 u odnosu na sabiranje po modulu 10 da ne davim mnogo, uzmimo g=3, 3 i 10 su uzajamno prosti, ok, generator dobijam samo sabiranjem po modulu 10, znaci: 3 mod 10 = 3 6 mod 10 = 6 9 mod 10 = 9 12 mod 10 = 2 ... teorija kaze da ce se ovako dobiti svi elementi grupe, tj. u nasem slucaju cifre od 0-9, nema ponavljanja I, sto je najlepse, tacno znas koji je i-ti clan, tj. mozes da ga izracunas, a kako je ovakav generator i bijekcija, da se napraviti i inverz, tj. moze se izracunati da je npr. cifra 9, dobijena kao treci clan niza. Ovu ideju treba malo razraditi i nema potrebe za smestanjem kodova u bazu. |
15. 02. 2006. | #3 |
Goran Pilipović
Sir Write-a-Lot
|
Posto nisi procitao od pocetka: traze se cifre 0..9 i karakteri a..z (case insensitive), ne samo cifre.
Iskreno, nisam bas najbolje shvatio tvoj predlog.
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman I don't always know what I'm talking about but I know I'm right! |
16. 02. 2006. | #4 |
Branimir Momcilovic
Qualified
Datum učlanjenja: 15.02.2006
Lokacija: Beograd
Poruke: 167
Hvala: 47
25 "Hvala" u 8 poruka
|
Nisam čitao celu diskusiju, a postavku problema sam pročitao detaljno.
Možda je moj odgovor bio malo štur, ajde da probam detaljnije. Pretpostavio sam da je svejedno da li si dobio kodove od cifara i slova, kakve tražiš, ili samo od cifara, jer kod od npr. 10 (ili više) cifara lagano možeš da prekodiraš u kod od 8 slova i cifara, ok? Izgleda i da je osim jedinstvenosti, bitno da kodovi ne mogu da se "provale", tj. da bude onemogućeno da se na osnovu određenog broja kodova generiše sledeći. Evo mog rešenja za 4 cifre od 0..9 (napisao bih i za 2 miliona, ali je potpuno isto). Izabereš prvi kod, neka je to 7777 (nije bitno kakav je) i uzajamno prost broj sa 10000, bilo bi idealno da je to prost broj, tako je najteže za razbijanje, ali za primer će biti dobar i 7811 i pustiš ovako nešto (nemam instaliran paint ): <?php $start = 7777; $seed = 7811; for($i=0; $i<100; $i++) { $code = ($start + $i * $seed) % 10000; echo $i, ' : ', $code, '<br>'; }?> Ovo ti daje (teorija brojeva garantuje) sve brojeve od 0 do 9999. Jasno dobijaćeš i brojeve sa manje cifara od 4, ali uvek možeš da dopišeš nule ispred. Još koja random cifra između da skreneš trag i izbegneš kodove tipa 1111, i prekodiraš dve tri cifre u slova da dobiješ ono što si tražio, to bi bilo to. Je l' sad bolje? P.S. Mislim da sam zaslužio veći rejting od "novi član"? |
16. 02. 2006. | #5 |
Goran Pilipović
Sir Write-a-Lot
|
Off Topic: Nešto sam sada umoran da čitam pažljivo, hoću samo da ti odgovorim za "novi član"... samo ti piši i promeniće ti se status onoliko brzo koliko doprinosiš forumu
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman I don't always know what I'm talking about but I know I'm right! |
16. 02. 2006. | #6 |
Python Ambassador
Master
|
Napiši implementaciju svog rešenja da uradimo benchmark i da vidimo imamo li novog šampiona, način rešavanja problema mi je interesantan.
Nekoliko puta si spomenuo termin "teorija brojeva". Koja i imaš li link ka dodatnim informacijama o njoj? My geek sense is tingling, ovo može da bude nešto jako interesantno. Eh da, imam jedno offtopic pitanje za tebe: Dolaziš nam sa PMF-a?
__________________
Python Ambassador of Serbia |
16. 02. 2006. | #7 |
Python Ambassador
Master
|
PHP kôd:
Formula za izračunavanje koju si naveo me je jako podsetila na ovu (A, B i M su const.): što je opšti oblik formule za LCG (linearni kongruentni generator) što je jedan od načina za generisanje pseudo-slučajnih brojeva. Iskreno rečeno, sad mi se tvoje rešenje i ne čini toliko hot. U ovom članku jasno piše da je korišćenje LCG-a u bilo kakvoj formi izrazito loša ideja u slučajevima kada je potreban visok kvalitet slučajnih brojeva (kao što je ovde slučaj). Ipak je Wikipedia: Mersenne Twister algoritam zakon za ovakve stvari PS: Eh, da ima li ko da preporuči neki softver i/ili MATLAB kod/funkciju/biblioteku/toolkit za spektralnu/frekvencijsku analizu (inače ću ponovo morati da pišem svoje funkcije)? Mogli bismo da napravimo benchmark kvaliteta rešenja koji nam daju programi, tj. ako ima zainteresovanih.
__________________
Python Ambassador of Serbia Poslednja izmena od Petar Marić : 16. 02. 2006. u 02:29. |
16. 02. 2006. | #8 |
Ivan Dilber
Sir Write-a-Lot
|
ovo je varijanta linearnog kongruentnog generatora... ako se dobro secam formula kojom se dobija sledeci pseudo-slucajn broj je:
x(i+1) = (A*x(i) + C) mod OPSEG gde je x(i) prethodni rnd broj (ili seed za prvi u nizu), a A i C proizvoljne konstante...ono za uzajamno proste brojeve je uslov za dobijanje max. duzine ciklusa... Koliko ja znam ovo se smatra kriptografski najslabijim pseudo-rnd generatorom (ne pitaj me zasto ga je najlakse razbiti, nemam pojma, ali tako pise u svim knjigama...) EDIT: ostao mi otvoren prozor, pa nisam video da je petar u medjuvremenu napisao ovo isto...sorry
__________________
Leadership is the art of getting people to want to do what you know must be done. |
|
|
Slične teme | ||||
Tema | Početna poruka teme | Forum | Odgovori | Poslednja poruka |
random + mysql | mega023 | PHP | 9 | 09. 03. 2010. 16:08 |
random select na velikoj tabeli | kodi | SQL baze podataka - Sponzor: Baze-Podataka.net | 14 | 09. 04. 2008. 12:46 |
random koji favorizuje | kodi | Programiranje | 16 | 29. 04. 2007. 21:09 |
java.util.Random security | Ivan | Programiranje | 0 | 02. 01. 2007. 18:43 |
Random image - preraditi za flash... | headcutter | (X)HTML, JavaScript, DHTML, XML, CSS | 4 | 02. 09. 2005. 22:14 |