Esercizio - Impronta di stringhe con un primo casuale e comunicazione

Testo. Alice e Bob hanno due stringhe di $n$ bit, viste come interi $a$ e $b$. Alice sceglie un primo $p$ uniformemente fra i primi $\le M$ e invia $(p,\ a\bmod p)$; Bob dichiara «uguali» se $a\bmod p=b\bmod p$.

1. Con $n=8$, $a=181$, $b=165$ e $p$ scelto uniformemente in $\{2,3,5,7,11,13\}$, calcolare esattamente la probabilità di errore. Ripetere con $b'=151$.
2. Dimostrare che l'errore è $\le n/\pi(M)$. Calcolarlo per $n=1000$, $M=10^6$ ($\pi(10^6)=78498$).
3. Quale $M$ garantisce con questo bound un errore $\le10^{-3}$ per $n=1000$? Quanti bit si comunicano rispetto a $1000$?
4. Migliorando il bound (il prodotto dei $130$ primi più piccoli supera $2^{1000}$), che errore si ottiene con $M=10^6$? E quante prove indipendenti con $M=10^6$ servono per scendere sotto $10^{-9}$ usando il bound semplice?

Teoria: Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici → (sezione 5); Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprintHashing con catene e costo atteso 1+alfa; famiglie universali (probabilità di collisione al più 1/m) e costruzione h(x)=((ax+b) mod p) mod m con dimostrazione; hashing perfetto a due livelli (spazio lineare, ricerca O(1) nel caso peggiore); filtri di Bloom: falsi positivi (1-e^(-kn/m))^k e k ottimo (m/n) ln 2; fingerprint di stringhe e numero di bit necessari.Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint →.

Soluzione

Punto 1. Se $a=b$ il test è sempre giusto. Qui $a\ne b$ e Bob sbaglia se $p\mid(a-b)$.

• $a-b=181-165=16=2^4$: l'unico primo divisore è $2$. I resti sono $a\bmod p=(1,1,1,6,5,12)$ e $b\bmod p=(1,0,0,4,0,9)$ per $p=2,3,5,7,11,13$: coincidono solo per $p=2$. Errore $1/6$.
• $a-b'=181-151=30=2\cdot3\cdot5$: coincidono per $p=2,3,5$ (resti $a$: $1,1,1$; $b'$: $1,1,1$) e non per $7,11,13$ ($6,5,12$ contro $4,8,8$). Errore $3/6=1/2$.

Punto 2. Sia $d=|a-b|$, con $1\le d<2^n$. Se $d$ avesse $t$ primi divisori distinti, tutti $\ge2$, sarebbe $d\ge2^t$, e da $d<2^n$ segue $t<n$, cioè $t\le n$. Scegliendo $p$ uniforme fra i $\pi(M)$ primi, cade fra quei $t$ con probabilità $t/\pi(M)\le n/\pi(M)$. Con $n=1000$ e $M=10^6$: $1000/78498=0{,}0127$.

Punto 3. Serve $\pi(M)\ge10^6$. Il milionesimo primo è $15\,485\,863$, quindi $M\approx1{,}55\cdot10^7$; con $M=1{,}6\cdot10^7$ si ha $\pi(M)=1\,031\,130$ e errore $\le0{,}00097$. Alice comunica $p$ (circa $\log_2M=24$ bit) e il resto (altri $\le24$ bit): circa $48$ bit invece di $1000$.

Punto 4. Il prodotto dei primi $130$ più piccoli è maggiore di $2^{1000}$ (la somma dei $\log_2$ dei primi $129$ vale $999{,}4$, quella dei primi $130$ vale $1009$): un $d<2^{1000}$ ha al più $129$ divisori primi distinti, quindi errore $\le129/78498=0{,}00164$. Con il bound semplice $0{,}0127$ e $k$ prove con primi indipendenti: $0{,}0127^k\le10^{-9}$ dà $k\ge\frac{20{,}72}{4{,}366}=4{,}75$, quindi $k=5$ (con $0{,}00164$: $k=4$, perché $0{,}00164^4=7\cdot10^{-12}$ e $0{,}00164^3=4{,}4\cdot10^{-9}$ non bastano).

Risultati: $1/6$ e $1/2$; errore $\le0{,}0127$ ($0{,}00164$ con il bound fine); $M=1{,}6\cdot10^7$, $48$ bit; $k=5$.

def primi(M):
    s = bytearray([1]) * (M + 1); s[0] = s[1] = 0
    for i in range(2, int(M**0.5) + 1):
        if s[i]: s[i * i::i] = bytearray(len(s[i * i::i]))
    return [i for i in range(M + 1) if s[i]]
q = [2, 3, 5, 7, 11, 13]
for b in (165, 151):
    print(b, [p for p in q if 181 % p == b % p])
P = primi(10**6)
print(len(P), 1000 / len(P), 129 / len(P))
import math
print(sum(math.log2(p) for p in P[:129]), sum(math.log2(p) for p in P[:130]))
print(len(primi(16 * 10**6)), 1000 / len(primi(16 * 10**6)))