T08
Alice e Bob mantêm cópias de um mesmo arquivo de $n$ bits de tamanho, onde \(n\) é razoavelmente grande. Imagine por exemplo que o arquivo tem 1G: nesse caso, $n=2^{33}$.
Alice e Bob querem fazer um teste de consistência: querem ver se suas cópias são idênticas. Entretanto, a transmissão de dados entre eles é custosa, e eles não querem transmitir os $n$ bits para fazer esse teste de consistência. Ele então seguem o protocolo a seguir.
Suponha que os bits de Alice são $(a_0,\dots,a_{n-1})$ e os bits de Bob são $(b_0,\dots,b_{n-1})$. Alice e Bob podem interpretar suas sequências de bits como sendo os inteiros $A=a_0+a_12+\dots+a_{n-1}2^{n-1}$ e $B=b_0+b_12+\dots+b_{n-1}2^{n-1}$. Eles querem verificar se $A=B$.
Seja $T=2n^2\log n$. Note que $T\leq n^3$. Vamos supor que Alice e Bob têm acesso a um gerador de números primos que, quando executado, devolve um primo $Q$ aleatório satisfazendo $2\leq Q\leq T$, com todos os primos satisfazendo essa condição equiprováveis.
O protocolo que Alice e Bob seguem é assim: ambos geram um primo $Q$ com $2\leq Q\leq T$ usando o tal gerador de primos comum que eles têm. Alice calcula $A'=A\bmod Q$ e envia esse valor para Bob. Bob verifica se $A'=B\bmod Q$. Se esse for o caso, Bob fica satisfeito e declara que seus arquivos coincidem. Caso contrário, Bob declara que os arquivos são diferentes.
Note que, nesse protocolo, Alice precisa enviar para Bob o número $A'=A\bmod Q$, que tem no máximo $1+\log_2Q\leq1+\log_2T\leq1+3\log_2n$ bits, que é muito menor que $n$ (que é o número de bits que Alice precisa enviar se ela enviar o arquivo inteiro).
Evidentemente, se os arquivos são iguais, Bob certamente declara que eles são iguais. Se os arquivos forem diferentes, há certa chance de o protocolo falhar de detectar a inconsistência dos arquivos.
Teorema 1. A probabilidade de ocorrer tal falha é menor que $3/2n$.
Voltando ao exemplo em que $n=2^{33}$ (arquivos de 1G), vemos que Alice só precisa enviar não mais que $1+3\log_2n=100$ bits. Ademais, a probabilidade de ocorrer uma falha é menor que $3/2n<2^{-32}<10^{-9}$. Assim, esse protocolo reduz o problema de verificar se dois arquivos de 1G são iguais à transmissão e verificação de no máximo $100$ bits. O preço pago é a possibilidade, de menos de $1$ em $10^9$, de não detectarmos uma possível inconsistência. Se você achar que $10^{-9}$ é uma probabilidade de falha muito grande, você pode, por exemplo, executar esse protocolo duas vezes (transmitindo $200$ bits no total) e garantir uma probabilidade de erro menor que $10^{-18}$.
Resta agora provar o teorema acima. Você fará isso nesse exercício. Para tanto, prove inicialmente o seguinte lema.
Lema 2. Se $C$ é um inteiro positivo com $C<2^n$, então $C$ tem menos que $n$ primos em sua decomposição em fatores primos.
Seja $\pi(x)$ o número de primos menores ou iguais a $x$. Sabe-se que $\pi(x)\geq x/\log x$ para todo $x\geq11$. (Você não precisa disso aqui, mas o Teorema dos Números Primos diz que $\pi(x)\sim x/\log x$, isto é, $\lim_{x\to\infty}\pi(x)(\log x)/x=1$.)
Lembre que $Q$ é um primo escolhido uniformemente ao acaso dentre todos os primos satisfazendo $2\leq Q\leq T=2n^2\log n\leq n^3$. Suponha que $A\neq B$, onde $A$ e $B$ são como acima. Prove que a probabilidade de $A\bmod Q=B\bmod Q$ ocorrer é menor que $n/\pi(T)$ e deduza o Teorema 1.
Entrega. Neste exercício, você deve entregar as provas do Lema 2 e do Teorema 1.