Newsgroup: it.comp.os.linux.development
Titolo: Permutazioni pseudocasuali.

Buonasera,
avrei bisogno di una mano: durante lo sviluppo del mio software è nata 
la necessità di costruire una funzione hash che data una chiave, 
restituisca una permutazione pseudocasuale univoca SOLO per quella chiave.
data la serie:
1 2 3 4 5
la chiave K
e la funzione hash P
P(1, K) = 2, P(2, K) = 3, P(3, K) = 5, ...
qualcuno ha qualche idea?
Grazie sentitamente.
=======================
Pomatto Luciano.


Una funzione che fa esattamente questo si chiama logaritmo discreto.
In supersintesi devi prendere un numero primo, es. 19 e le sue radici
primitive che per il 19 sono (2,3,10,13,14,15). (Credo che se vuoi, trovi le
routine gia' fatte, e' un algoritmo molto noto in crittografia.)
Le radici primitive sono quei numeri che hanno questa proprieta':
usiamo Num.Primo=19 e rad.primord(19)=13
13^i mod 19 = k
Per ogni i da 1 a 18 ottengo un k sempre diverso. k poi e' compreso tra 0 e
18 (essendo un modulo 19).
cioe':
13^1 mod 19 =13
13^2 mod 19 =17
13^3 mod 19 =12
13^4 mod 19 =4
13^5 mod 19 =14
........
13^17 mod 19 =3
13^18 mod 19 =1
MORALE:
(con qualche aggiustamento) la funzione che ti serve e'
k = F(i) = a^i mod p
Dove p e' un numero primo e a e' una sua base primordiale.
Avrai che i viene trasformato in k e puoi usare un p fisso e usare a (la
base primordiale) come chiave perche' se invece che 13 usi 15 la permutaz.
e' tutta diversa.
Ciao
Ux
----------------------
Niente e' piu' simile all'identico di cio' che e' uguale alla stessa cosa.
(Jacovitti)

qualcuno ha qualche idea?
Usi la chiave come seme di un generatore di numeri casuali, usando
quello fornito da libc se non sai costruirne uno nuovo (e non sai farlo,
fidati).
Poi parti dalla permutazione identica:
posizione   1 2 3 4 5 
elemento    1 2 3 4 5
e scegli casualmente due posizioni, e ne scambi gli elementi. Ripeti
questo passaggio un certo numero di volte, e hai ottenuto la tua
permutazione su chiave.
Nota: il numero di volte in cui scambiare gli elementi è critico, se
sono troppo pochi rischi di ottenere una permutazione poco
permutata. Una ottimizzazione è quella di scandire la prima metà del
vettore, e scambiare ogni elemento con un elemento scelto in modo
casuale nella seconda metà (ricordo una volta un astuto codice di Marco
d'Itri che faceva proprio accussì).
Inoltre, la funzione che a partire dalla chiave genera il seme per
inizializzare il generatore di numeri casuali è critica anch'essa, la
cosa migliore che puoi fare è che la chiave iniziale sia essa stessa un
numero a 32 bit con segno, e passarlo direttamente a srandom().
-- 
"L'Italia è un interessante esempio di avanguardia teatrale" (Gore Vidal)
Per rispondermi, ricordati di togliere il nome del poeta.

 wrote in message
slrnb2q2m3.n...@localhost.localdomain...


diventa anzi abbastanza probabile.
Per chiavi di generazione delle permutazioni: no, un seme è sempre un
seme se usi un buon generatore di numeri casuali.
Per un numero n piccolo di elementi da permutare: il numero massimo
di permutazioni possibili rimane sempre n!.


 di permutazioni possibili rimane sempre n!.
Vero, ma dipende quante ne utilizzi.
Se qli elementi sono pochi, tipo 5, hai 120 permutazioni possibili. Se ne
utilizzi diciamo 60 o 70 credo che la probabilita' di collisione sia
abbastanza alta (dovrei fare 2 conti).
Ciao
Ux


 di permutazioni possibili rimane sempre n!.
Perche', se n aumenta, invece che accade? 
-- 
#include <stdio.h>/* (C) BW2K+2 This code is released under GPL 2+ */
int main(){char c[]={98,108,97,99,107,119,111,108,102,64,100,101,115,112,
97,109,109,101,100,46,99,111,109,32,119,101,98,46,116,105,115,99,97,108,
105,46,105,116,47,98,108,97,107,119,111,108,102,0};printf("%s\n",c);}

Perche', se n aumenta, invece che accade? 
Definitivamente, n! > 2^31


abbastanza alta (dovrei fare 2 conti).
Quindi, se hai 5 elementi, hai 120 permutazioni possibili, e il numero
di chiavi magari sarà 2^31, quindi chiavi diverse finiscono in
permutazioni uguali. Se hai 70 elementi, hai 10^100 permutazioni
possibili e quindi una chiave tra 2^31 produce una permutazione che è
molto probabile che sia sua specifica ed univoca, se il mescolamento
è deterministico rispetto alla chiave ed avviene a lungo.


 Definitivamente, n! > 2^31
ah, be', da come era scritto avevo capito che cambiasse la legge delle 
permutazioni


grazie a tutti.
adesso mi mettero sotto.
--== Pomatto Luciano   ==--
   == 
red...@libero.it
 ==

 permutazioni uguali. Se hai 70 elementi, hai 10^100 permutazioni
Non ci capiamo. Intendevo dire : Se hai 5 elementi li puoi permutare in 120
modi distinti. Se utilizzi 60 o 70 di queste permutazioni (sempre di 5
elementi) hai gia' una alta probab. di collisione, perche' ogni perm. nel
tuo sistema genera una permutazione a se', indipendente dalle altre, e
quindi potenzialmente identica a qualche altra gia' generata con chiave
diversa.


diversa.
L'obiezione č irrilevante. Se hai 5 elementi da permutare, hai 5
elementi da permutare, fine del dibattito su quanti pochi siano.
-- 
"L'Italia č un interessante esempio di avanguardia teatrale" (Gore Vidal)


 e' tutta diversa.
essendo p, per forza un numero primo, potrebbe risultare un po' scomodo:
se ho un insieme di ventuno elementi, devo prendere come p il prossimo
numero primo successivo al ventuno, creando cosě permutazioni sbagliate.
e soprattutto: perchč č necessario che p sia un numero primo e a una sua
radice primordiale?
Grazie comunque.
-==Pomatto Luciano==--