Несложная криптографическая задача
Difference between ru3 and ru4, changed 117 character(s)
Пару месяцев назад я придумал одну задачу. Рассказал ее коллеге, и мы вместе нашли некое подобие решения. Теперь мне бы хотелось услышать какие-либо новые идеи.↵

Условие: Алиса и Боб загадали по **однобайтовому** числу (пусть эти числа будут называться $a$ и $b$ соответственно). Требуется придумать протокол общения между Алисой и Бобом, позволяющий им понять: равны ли $a$ и $b$? При этом хочется, чтобы Алиса и Боб выдали друг другу как можно меньше информации о своих числах (в идеале — только сам факт равенства/неравенства). Предполагается, что Алиса и Боб будут строго следовать протоколу. Предполагается, что посторонних участников в задаче нет.↵

Прошу писать идеи решения в комментариях и прятать их под спойлеры.↵

**UPD.** [user:hellman1908,2016-01-31] предложил [решение](http://mirror.codeforces.com/blog/entry/23195?locale=ru#comment-276063), которое на первый взгляд удовлетворяет вышеописанному требованию к идеальному решению.


**UPD2.** [OWNAGE](http://mirror.codeforces.com/blog/entry/23195?locale=ru#comment-276107) от [user:eatmore,2016-02-01].

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian AlexanderBolshakov 2016-02-02 03:45:09 123
ru4 Russian AlexanderBolshakov 2016-02-01 00:10:06 117
ru3 Russian AlexanderBolshakov 2016-01-31 22:16:29 215 Мелкая правка: 'йлеры.\n\nUPD. [user:hel' -> 'йлеры.\n\n**UPD.** [user:hel'
ru2 Russian AlexanderBolshakov 2016-01-31 19:16:36 4 Мелкая правка: 'гадали по однобайтовому числу (пу' -> 'гадали по **однобайтовому** числу (пу'
ru1 Russian AlexanderBolshakov 2016-01-31 18:45:07 762 Первая редакция (опубликовано)