Hashing astut? P78794

Hashing astut?

Abans de plantejar aquest problema, us recordem (o informem) que:

Donats dos enters a i b, en C++ (ab)és el XOR d’a i b. És a dir, n’és el “or exclusiu bit a bit”: el resultat d’operar cada parell de bits és 1 sii els dos bits són diferents. Per exemple, (912)\(=\)(\(1001_2\)\(1100_2\))\(= 0101_2 =\) 5.

Donats dos enters x i n, en C++ (x<<n)és el resultat de desplaçar xn bits cap a l’esquerra. Si no hi ha sobreiximents, dóna el resultat de multiplicar x per 2 elevat a n. Per exemple, (9<<2)\(=\) (\(1001_2\)<<2)\( = 100100_2 =\)36.

Ara, el problema. L’Edgar ha descobert un nou algorisme de hashing al qual li veu un gran futur en aplicacions criptogràfiques. Semblant a tants altres métodes, combina moltes operacions de bits, per la qual cosa podria ser complicat recuperar la informació original.

L’Edgar ha decidit que treballarà amb enters de \(B = 30\) bits (és a dir, módul \(2^B\)). Donats dos enters \(a\) i \(b\), defineix:

L’Edgar ens assegura (i té raó) que donats \(a\) i \(c = h(a, b)\), només hi ha una \(b\) possible. Ell creu que el seu mètode és prou segur, és a dir, que no es pot obtenir \(b\) eficientment a partir d’\(a\) i de \(c\). Demostreu que l’Edgar és un palomo.

Entrada

L’entrada consisteix en diversos casos, cadascun amb \(a\) i \(c\), dos enters entre 0 i \(2^{30} - 1\).

Sortida

Per a cada cas, escriviu la \(b\) corresponent.

Author

Izan Beltrán

© Jutge.org, 2006–2024