Difficoltà a comprendere pochi passaggi nella prova: "La classe $ \ mathscr {h} _ {p, m} $ di funzioni hash è universale"
https://cs.stackexchange.com/questions/127691
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Stavo attraversando l'introduzione del testo agli algoritmi di Cormen et. al. Dove mi sono imbattuto nel seguente estratto per quanto riguarda la prova detta e i passaggi in cui ho sentito difficoltà sono contrassegnati con $ \ pugnale $ e $ \ pugnale \ pugnale $ rispettivamente.
Progettazione di una classe universale di funzioni hash
$ p $ è un numero primo abbastanza grande in modo che ogni possibile chiave $ k $ è in La gamma $ 0 $ a $ P - 1 $ , incluso. Let $ Z_P $ Denota il set $ \ {0, 1, ..., P - 1 \} $ e Let $ Z_P ^ * $ Denna il set $ \ {1, 2, ..., P - 1 \} $ . Perché del presupposto che la dimensione dell'universo delle chiavi è maggiore del numero di slot $ m $ nella tabella hash, Abbiamo $ p> m $ .
Ora definiamo la funzione hash $ h_ {a, b} $ per qualsiasi classe
$ h_ {a, b}= ((a.k + b) \ mod p) \ mod m $ .
La famiglia di tutte queste funzioni di tali hash:
$$ \ mathscr {h} _ {p, m}={h_ {a, b}: a \ in z_p ^ *, b \ in z_p \} $ $
.
.Teorema: la classe $ \ mathscr {h} _ {p, m} $ delle funzioni hash è universale.
.
Prova:
Considera due tasti distinti $ k $ e $ l $ da $ Z_P $ , in modo che $ k \ neq l $ . Per una determinata funzione hash $ h_ {a, b} $ lasciamo
$$ r= (ak + b) \ mod P $$ ,
$$ s= (al + b) \ mod P $$ .
Note per la prima volta che $ r \ neq s . Perché? Osservare questo
$$ R - S= A (K - L) (\ mod P) $$ .
Segue che $ Г \ neq s $ perché $ p $ è Prime ed entrambi $ A $ e $ (k - l) $ sono diverso da zero modulo $ p $ , e quindi il loro prodotto deve anche essere diverso da zero modulo $ p $
Pertanto, durante il calcolo di qualsiasi classe
$$ A= (((R - S) ((K - L) ^ {- 1} \ Mod P)) \ mod P $$ , < / P >.
$$ B= (R - AK) \ mod P $$ ,
Dove $ ((K - L) ^ {- 1} \ mod P) $ Denota l'esclusivo inverso multiplicativo, Modulo P, di $ k - l $ . Poiché ci sono solo $ P (P - 1) $ Possibili coppie $ (r, s) $ con $ Г \ neq s $ , c'è una corrispondenza one-to-one tra coppie $ (A, B) $ < / span> con $ a \ neq 0 $ e coppie $ (r, s) $ con $ r \ neq s . Pertanto, per qualsiasi coppia di ingressi $ k $ e $ l $ , se prendiamo <="container math"> $ (a, b) $ uniformemente a caso da $ z_p ^ * \ volte z_p $ , la coppia risultante < class="container math"> $ (r, s) $ è ugualmente probabile che sia qualsiasi coppia di valori distinti Modulo p.
si segue quindi la probabilità che tasti distinti $ k $ a
ND $ L $ Bollide è uguale alla probabilità che $ r \ equiv s (\ mod m) $ quando $ r $ e $ s $ sono scelti casualmente come valori distinti modulo $ P $ . per un determinato valore di $ R $ , della $ P - 1 $ Possibili valori rimanenti per $ s $ , il numero di valori $ s $ tale che $ s \ neq r $ e $ s \ equiv r (\ mod m) $ è al massimo $ ^ {\ pugnale \ pugnale} $$$ \ lceil P / m \ rceil - 1 <(((P + m - 1) / m) - 1 $$ $$= (P-1) / m $$ .
La probabilità che $ s $ collids con $ r $ quando è ridotto Modulo $ m $ è al massimo $ ((P - L) / m) / (P - 1)= 1 / m $ .
Pertanto, per qualsiasi coppia di valori distinti $ k, l \ in z_p $ ,
$$ PR \ {H_ {A, B} (K)= H_ {A, B} (L) \} \ Leq 1 / m $$
In modo che $ \ mathscr {h} _ {p, m} $ è effettivamente universale.
.
Dubbi:
Non ho potuto capire le seguenti affermazioni nella prova:
$ \ dagger $ : ciascuna delle possibili $ P (P - 1) $ Scelte per la coppia $ (a, b) $ con $ а \ neq 0 $ rendisce un altro Coppia risultante $ (r, s) $ con $ r \ neq s , dal momento che possiamo risolvere per $ A $ e $ B $ Dato $ R $ < / span> e $ s $
Perché, "Possiamo risolvere per $ A $ e $ B $ Dato
.
$ \ dagger \ pugnale $ : per un determinato valore di $ r $ , della $ P - 1 $ Possibili valori rimanenti per $ s $ , il numero di valori <="container di matematica"> $ s $ tale che $ s \ neq r $ e $ s \ Equiv R (\ mod m) $ è al massimo $ \ lceil p / m \ rceil - 1 $ .
Come otteniamo il termine $ \ lceil p / m \ rceil - 1 $ ?
Soluzione
Vogliamo mostrare che se $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ quindi
$ \ PR \ Limits _ {(a, b) \ in \ mathbbs {z} _p ^ * \ volte \ mathbb {z} _p} [AK_1 + B \ Equiv AK_2 + b \ Pmod m] \ le \ frac {1} {m} $ .
DOVE Sia l'aggiunta che la moltiplicazione sono preformate in $ \ mathbb {z} _p $ .
Iniziamo mostrando che se $ A \ SIM U (Z_P ^ *) $ e $ B \ Sim U (Z_P) $ quindi per tutti $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ , $ (AK_1 + B, AK_2 + B) $ è uniformemente distribuito su $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \} $ (cioè $ h (k_1) $ e $ h (k_2) $ sono uniformi congiuntamente su coppie con voci diverse, in cui la casualità è sulla scelta di $ h $ ). Questo è immediato dal fatto che per tutti $ (c_1, c_2) \ in \ mathbb {z} _p ^ 2 $ con $ c_1 \ neq c_2 $ , il seguente sistema di equazioni lineari:
$ \ Begin {allinea *} & ak_1 + b= c_1 \\ & ak_2 + b= c_2 \ end {allinea *} $
ha una soluzione unica sulle variabili $ (A, b) \ in z_p ^ * ^ time \ mathbbb {z} _p $ . Sottraendo la seconda equazione dai primi rendimenti $ A (k_1-k_2)= c_1-c_2 $ , poiché $ k_1-k_2 $ è diverso da zero possiamo moltiplicare entrambi i lati con il suo inverso e ottenere $ a= (k_1-k_2) ^ {- 1} (c_1-c_2) $ . Se $ c_1 \ neq c_2 $ , quindi questa è una soluzione diversa da zero per $ a $ , e possiamo Estratto $ B $ da una qualsiasi delle due equazioni. Pertanto, per ogni coppia $ (c_1, c_2) $ con $ c_1 \ neq c_2 $ Ci sono unici $ (a, b) \ in z_p ^ * \ volte \ mathbbb {z} _p $ in modo tale che $ \ Big ( H_ {A, B} (K_1), H_ {A, B} (K_2) \ Big)= (c_1, c_2) $ . Questo risolve la tua prima domanda.
Ora, divide $ \ mathbb {z} _p $ in $ \ lceil p / m \ rceil $ Secchi, $ B_1, ..., B_ {l=lceil P / m \ rceil} $ come segue: $ B_1={0,1, ..., M-1 \}, B_2={m, M + 1, ..., 2m-1 \} $ , ..., < Span Class="Math-Container"> $ B_L={M \ LFloor P / M \ RFloor, M \ Lceil P / M \ rceil + 1, ..., P-1 \} $ . Si noti che ogni secchio tranne l'ultimo è di dimensioni $ m $ e nessun due elementi nello stesso secchio sono equivalenti modulo $ m $ . Concludiamo che il numero di coppie diverse in $ \ {(x, y) \ in \ mathbbs {z} _p ^ 2 | x \ neq y \} $ che sono equivalenti Modulo $ m $ è al massimo $ P (\ Lceil P / M \ RCeil-1) $ , poiché dopo aver scelto il primo elemento, sei lasciato con $ \ lceil p / m \ rceil-1 $ Elementi da scegliere (è necessario scegliere un secchio diverso e ogni secchio fornisce al massimo un candidato). Ricorda che $ \ Big (H_ {A, B} (K_1), H_ {A, B} (K_2) \ Big) \ SIM U (\ {(X, Y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \}) $ , quindi possiamo finalmente concludere:
$ \ PR \ Limits _ {(a, b) \ in \ mathbbs {z} _p ^ * \ volte \ mathbbs {z} _p} \ sinistra [h_ {a, b} (k_1)= h_ {a, b} (k_2) \ pmod m \ destra]=frac {p (\ lceil p / m \ rceil-1)} {p (P-1)} \ le \ frac {1} {m} $
Nota che consentendo $ A $ per prendere il valore $ 0 $ rende solo la nostra analisi più facile, poiché semplifica la nostra analisi, da allora ora $ \ Big (h (k_1), h (k_2) \ big) $ è uniforme congiuntamente su $ \ mathbb { Z} _p ^ 2 $ , ma c'è una probabilità aggiuntiva di $ \ frac {1} {p} $ che $ A= 0 $ Ei nostri hash saranno equivalenti modulo $ m $ , quindi in questo caso dovremo accontentarci di un $ O (\ frac {1} {m}) $ Legato sulla probabilità di collisione.
