Пятница. Вечер. Уставшие после четырех пар лекций в университете, одногруппники Петя и Лена возвращались домой. Друзья собирались вместе поужинать, отдохнуть пару часов, а затем отправиться на рыбалку. В покер-рум. Но этим планам не было суждено сбыться — поднимаясь в лифте, ребята внезапно услышали странный скрежет и ощутили резкий толчок. Свет погас, и лифт остановился. Вызванный нажатием кнопки сотрудник технической поддержки пообещал постараться уговорить уже празднующего пятницу лифтера прийти узникам на помощь. «Ну что, чем будем заниматься?» — раздосадованным голосом спросил Петя, которого совершенно не прельщала перспектива провести весь вечер в темном, тесном, грязном и, что самое скверное, застрявшем лифте. «Сыграем в покер!» — неожиданно услышал он в ответ.
Само собой разумеется, что карт под рукой ни у кого не оказалось. Пытаться сделать карты из подручных материалов мешает природная лень и искусственная темнота. В этой безвыходной ситуации Лена сделала довольно оригинальное предложение:
-Петь, давай играть в покер в уме!
-Это шутка?
-Нет, не шутка! Ты когда-нибудь играл в уме в шахматы?
-Без доски? Было дело. Но, как правило, после выхода из дебюта мы были не в состоянии запомнить позицию, не говоря уже о невозможности просчета сложных комбинаций.
-Вот! Точно так же можно попробовать играть в покер без карт.
-Подожди, ничего не понимаю. В шахматах любой ход делается в соответствии с правилами передвижения фигур, причем эти правила не допускают никакого элемента случайности. Но в покере-то все не так! Какие карты сдаются игрокам на префлопе? Как определяются флоп, терн и ривер?
-Не торопись, давай по порядку. Очевидно, что тип нашей игры – heads up. Предположим, что у нас есть с тобой по 10 долларов. Процесс торговли в уме можно вести точно так же, как и в обычном покере. Проблема состоит лишь в том, чтобы научиться моделировать раздачу карт. Сначала раздаем карты на префлоп. Нужно сделать так, чтобы ты знал свои карты, но не знал мои. Давай что-нибудь придумаем!
-Это должно быть просто. Предлагаю пронумеровать в уме все 52 карты натуральными числами от 1 до 52 в некотором известном нам с тобой порядке. Например, пусть 1 – это двойка пик, 2 – это двойка треф, 3 – двойка бубей, ... , 52 – это туз червей. Я перемешаю колоду, загадав какую-нибудь кодирующую функцию K(n). Эта функция будет известна только мне. Затем я сообщу тебе 52 следующих числа: K(1), K(2), ... , K(52). После этого ты выберешь два числа из этих пятидесяти двух и назовешь их мне. Дальше я применю к этим числам декодирующую функцию K-1(n), то есть функцию, обратную к функции K(n). Получатся два числа от 1 до 52, которым сопоставлены некоторые две карты в соответствии с нашей начальной нумерацией. Это и будут мои карты, с ними я начинаю игру на префлопе. Точно также карты можно сдать и для тебя!
-Может быть, приведешь пример?
-Хорошо. Допустим, я загадал кодирующую функцию K(n) = 2n + 1 (ты ее не знаешь!). Я говорю тебе 52 числа: 3, 5, 7, ... , 105. Ты произвольным образом выбираешь для меня ровно два числа, например, 7 и 103. Так как K-1(n) = (n – 1)/2, то K-1(7) = 3 и K-1(103) = 51. Числу 3 соответствует двойка бубей, а числу 51 – туз бубей. Вот моя рука на префлопе!
-Здорово! То есть, нет, не очень... Если мы провернем такую операцию два раза – для тебя и для меня, – то получится, что нам сдают карты из разных колод! Вдруг мы сдадим друг другу одни и те же карты? Не годится! Колода должна быть одна.
-Да, ты права. Хорошо, давай колода будет моей, то есть ты сдаешь мне две карты точно так же, как и раньше. Вычеркнем из множества {K(1), K(2), ... , K(52)} два названных тобой числа, соответствующих моим картам. В нашем примере этими числами являются 7 и 103, то есть K(3) и K(51). Останется 50 чисел. Теперь надо сдать две карты тебе. Это проблематично, потому что, во-первых, тебе неизвестна функция K(n), и значит, ты не сможешь сдать себе карты сама, а, во-вторых, я не должен знать твои карты, поэтому я не смогу сдать карты тебе.
-Так-так-так... Мне кажется, что эти две проблемы можно решить. Ведь я тоже могу закодировать оставшиеся 50 карт и предоставить тебе выбор двух карт для меня. Я выберу кодирующую функцию J(n), которая будет известна только мне, вычислю 50 чисел J(K(1)),..., J(K(52)) (за исключением J(K(3)) и J(K(51))) и сообщу эти числа тебе. Поскольку ты знаешь функцию K(n), то ты сможешь легко получить из чисел вида J(K(n)) числа вида J(n).
-Не совсем так. Я смогу вычислить значения J(1),...,J(52), применив свою декодирующую функцию K-1(n), только в том случае, если J(K(n)) = K(J(n)) для любого n от 1 до 52. Другими словами, наши с тобой кодирующие функции K(n) и J(n) должны быть коммутативны относительно операции суперпозиции (подстановки друг в друга). Если это условие выполняется, то по твоим 50 числам вида J(K(n)) я определю 50 чисел вида K-1(J(K(n))) = K-1(K(J(n))) = J(n). Заметь, что я не знаю твою функцию J(n), поэтому я не знаю, какие карты скрываются за каждым из 50 чисел J(1), J(2), J(4), ..., J(50), J(52). Тогда я смогу произвольным образом вытащить из этого множества любые два числа, например J(1) и J(4), и назвать эти два числа тебе. Так как ты знаешь свою кодирующую функцию J(n), то, применив декодирующую функцию J-1(n), ты обнаружишь, что я выбрал для тебя карты под номерами J-1(J(1)) = 1 и J-1(J(4)) = 4, то есть двойку пик и двойку червей. С префлопом мы разобрались!
-Подожди, есть еще одна проблема. Мы загадываем K(n) и J(n) втайне друг от друга. Как решить проблему с коммутативностью наших кодирующих функций? Далеко не любые две функции обладают этим свойством.
-А что если мы будем выбирать кодирующие функции только определенного вида? Например, класс функций AI(n) = n·10I (I – натуральное) таков, что для любых натуральных K и J функции K(n) = n·10K и J(n) = n·10J коммутативны относительно суперпозиции, так как J(K(n)) = n·10K ·10J = K(J(n)).
-Супер! Итак, перед началом игры мы вместе тобой выбираем семейство коммутативных кодирующих функций, а потом каждый из нас втайне выбирает закрытый ключ – одну функцию из этого семейства. Проворачиваем наш алгоритм и... всё, карты на префлопе розданы! Определить флоп, терн и ривер еще проще, так как эти карты не нужно ни от кого скрывать! Кажется, мы почти готовы сыграть первую раздачу!
-Лен, знаешь о чем я подумал? Функции из семейства AI(n) на самом деле плохие. Вот представь: я называю тебе в качестве чисел K(1), K(2), ... , K(52) следующие числа: 10000000, 20000000, 30000000, ... , 520000000. Зная, что моя кодирующая функция имеет вид n·10I, ты моментально вычислишь мой закрытый ключ: K = 7, K(n) = n·107. После этого ты сможешь сдать мне любые карты по твоему выбору!
-Значит, нужно выбирать такое семейство AI(n), чтобы по числу n (от 1 до 52) и коду K(n) было бы невозможно расшифровать закрытый ключ К за обозримое время с помощью вычислительных методов.
-Именно! Если мы договоримся перед игрой выбирать кодирующие функции из семейства AI(n) = nK, то по числу 506623120463 ты вряд ли быстро определишь, что это есть ни что иное, как 477. Такое кодирование уже достаточно тяжело взломать. Следовательно, можно быть уверенным в том, что соперник не знает твоих карт.
-А что делать, например, с числами вида 10K? Увидев число, оканчивающееся на несколько нулей, я сразу получу некоторую информацию относительно закодированной карты, а именно, это будет одна из следующих карт: 10, 20, 30, 40, 50.
-Это хорошее замечание! Получается, что первоначальная нумерация карт числами от 1 до 52 не совместима с кодирующими функциями вида AI(n) = nK. Нужно нумеровать карты так, чтобы никакое свойство первоначальной нумерации карт не сохранялось после их кодирования. В частности, не должно сохраняться упомянутое тобой свойство числа оканчиваться на ноль.
-Петь, позволь один нескромный вопрос. Скажи, а я могу быть на 100% уверена в тебе?
-Хех, это ты к чему?!
-Я первая спросила, не уходи от ответа.
-Ну, не знаю... В принципе, да.
-Так “да” или только “в принципе”?
-Лен, что происходит? Что за допрос ты мне устраиваешь?
-Не горячись Мне пришла в голову одна мысль. Скажи, а ты уверен, что у нас уже в первой раздаче не случится префлоп олл-ин АА против АА?
-Это очень маловероятно... Если, конечно, мы играем честно.
-Вот! Можно ли мне быть уверенной в том, что ты не сжульничаешь, выдав свои A2 за пару тузов?
-Для корректности покера в уме нам надо не полагаться друг на друга, а обеспечить механизм честной игры. Например, можно обязать нас с тобой после каждой раздачи, закончившейся шоудауном, рассекречивать свой закрытый ключ. Это позволит проверить, соответствуют ли названные нами на шоудауне карты тем, которые были розданы в действительности.
-Но я могу обмануть тебя, назвав другой закрытый ключ, соответствующий двум тузам.
-Надо сделать так, чтобы ты не смогла быстро подобрать ключ, соответствующий двум тузам. Появляется еще одно необходимое условие на семейство кодирующих функций AI(n): для любых ni и nl из начальной нумерации карт числами n1 ,..., n52 невозможно за обозримое время подобрать с помощью вычислительных методов два ключа K и J, такие, что K(ni) = J(nl).
-Честно говоря, я уже начинаю немного запутываться. Давай аккуратно опишем алгоритм покера вслепую.
-Нет проблем! Итак, вот очередность наших действий:
1) мы с тобой договариваемся относительно начальной нумерации всех 52 карт числами n1 ,..., n52;
2) мы с тобой договариваемся относительно семейства кодирующих функций AI(n);
3) я выбираю свой закрытый ключ K – функцию K(n) из семейства AI(n);
4) я вычисляю значения K(n1), ... , K(n52) и сообщаю их тебе;
5) ты выбираешь произвольным образом для меня два числа из множества чисел {K(n1), ... , K(n52)};
6) я декодирую эти два числа с помощью функции K-1(n) и узнаю свои две карты;
7) ты выбираешь свой закрытый ключ J – функцию J(n) из семейства AI(n);
ты вычисляешь значения выражений вида J(K(nl)) для 50 оставшихся карт и сообщаешь их мне;
9) я с помощью функции K-1(n) вычисляю 50 значений выражений вида J(nl);
10) я выбираю произвольным образом два числа из этих 50 чисел и сообщаю их тебе;
11) ты декодируешь эти два числа с помощью функции J-1(n) и узнаешь свои две карты;
12) раунд торговли на префлопе.
Если игра продолжается дальше, то:
13) я выбираю произвольным образом три числа из оставшихся 48 чисел вида J(nl) и сообщаю их тебе;
14) ты декодируешь эти три числа с помощью функции J-1(n) и сообщаешь их мне, мы узнаем флоп;
15) раунд торговли на флопе;
Если игра продолжается дальше, то:
16) я выбираю произвольным образом одно число из оставихся 45 чисел вида J(nl) и сообщаю его тебе;
17) ты декодируешь это число с помощью функции J-1(n) и сообщаешь его мне, мы узнаем терн;
1 раунд торговли на терне;
Если игра продолжается дальше, то:
19) я выбираю произвольным образом одно число из оставихся 44 чисел вида J(nl) и сообщаю его тебе;
20) ты декодируешь это число с помощью функции J-1(n) и сообщаешь его мне, мы узнаем ривер;
21) раунд торговли на ривере;
Если игра доходит до шоудауна, то:
22) каждый из нас объявляет свои две карты;
23) определяется победитель раздачи, он забирает банк;
24) каждый из нас сообщает свой закрытый ключ для проверки честности игры.
-Хорошо, структура игры теперь понятна. Остается вопрос технического характера, но без ответа на него у нас с тобой все равно ничего не получится: как следует выбирать начальную нумерацию карт и семейство кодирующих функций AI(n), чтобы они удовлетворяли всем необходимым требованиям? Давай вкратце напомню все полученные нами ограничения:
1) коммутативность функций AI(n);
2) отсутствие сохранения свойств начальной нумерации при кодировании;
3) невозможность быстрой расшифровки кода;
4) невозможность жульничества путем замены закрытого ключа.
У тебя есть идеи, как решать задачу выбора начальной нумерации карт и семейства кодирующих функций?
Петя не успел рассказать Лене свои мысли по этому поводу. Зажегся свет, и лифт поехал вверх настолько же неожиданно, насколько он остановился пару часов назад. Надо ли говорить, что ребята оставили свою увлекательную дискуссию до лучших времен, предпочтя расслабиться после сегодняшнего приключения.
Алгоритм для игры в покер вслепую был предложен в 1979 году исследователями в области криптографии Adi Shamir, Ronald Rivest и Leonard Adleman (Massachusetts Institute of Technology) в статье «Mental Poker». Ее рекомендуется прочитать всем желающим узнать ответ на последний вопрос Лены. А цель данной статьи – знакомство читателей с рядом проблем, которые возникают при попытке моделирования покера в уме, – будем считать достигнутой.
#6 WhiteFаnG @ 10.11.09 15:18 [пожаловаться]
Чем заняться в застрявшем лифте, или Покер в уме.
Пятница. Вечер. Уставшие после четырех пар лекций в университете, одногруппники Петя и Лена возвращались домой. Друзья собирались вместе поужинать, отдохнуть пару часов, а затем отправиться на рыбалку. В покер-рум. Но этим планам не было суждено сбыться — поднимаясь в лифте, ребята внезапно услышали странный скрежет и ощутили резкий толчок. Свет погас, и лифт остановился. Вызванный нажатием кнопки сотрудник технической поддержки пообещал постараться уговорить уже празднующего пятницу лифтера прийти узникам на помощь. «Ну что, чем будем заниматься?» — раздосадованным голосом спросил Петя, которого совершенно не прельщала перспектива провести весь вечер в темном, тесном, грязном и, что самое скверное, застрявшем лифте. «Сыграем в покер!» — неожиданно услышал он в ответ.
Само собой разумеется, что карт под рукой ни у кого не оказалось. Пытаться сделать карты из подручных материалов мешает природная лень и искусственная темнота. В этой безвыходной ситуации Лена сделала довольно оригинальное предложение:
-Петь, давай играть в покер в уме!
-Это шутка?
-Нет, не шутка! Ты когда-нибудь играл в уме в шахматы?
-Без доски? Было дело. Но, как правило, после выхода из дебюта мы были не в состоянии запомнить позицию, не говоря уже о невозможности просчета сложных комбинаций.
-Вот! Точно так же можно попробовать играть в покер без карт.
-Подожди, ничего не понимаю. В шахматах любой ход делается в соответствии с правилами передвижения фигур, причем эти правила не допускают никакого элемента случайности. Но в покере-то все не так! Какие карты сдаются игрокам на префлопе? Как определяются флоп, терн и ривер?
-Не торопись, давай по порядку. Очевидно, что тип нашей игры – heads up. Предположим, что у нас есть с тобой по 10 долларов. Процесс торговли в уме можно вести точно так же, как и в обычном покере. Проблема состоит лишь в том, чтобы научиться моделировать раздачу карт. Сначала раздаем карты на префлоп. Нужно сделать так, чтобы ты знал свои карты, но не знал мои. Давай что-нибудь придумаем!
-Это должно быть просто. Предлагаю пронумеровать в уме все 52 карты натуральными числами от 1 до 52 в некотором известном нам с тобой порядке. Например, пусть 1 – это двойка пик, 2 – это двойка треф, 3 – двойка бубей, ... , 52 – это туз червей. Я перемешаю колоду, загадав какую-нибудь кодирующую функцию K(n). Эта функция будет известна только мне. Затем я сообщу тебе 52 следующих числа: K(1), K(2), ... , K(52). После этого ты выберешь два числа из этих пятидесяти двух и назовешь их мне. Дальше я применю к этим числам декодирующую функцию K-1(n), то есть функцию, обратную к функции K(n). Получатся два числа от 1 до 52, которым сопоставлены некоторые две карты в соответствии с нашей начальной нумерацией. Это и будут мои карты, с ними я начинаю игру на префлопе. Точно также карты можно сдать и для тебя!
-Может быть, приведешь пример?
-Хорошо. Допустим, я загадал кодирующую функцию K(n) = 2n + 1 (ты ее не знаешь!). Я говорю тебе 52 числа: 3, 5, 7, ... , 105. Ты произвольным образом выбираешь для меня ровно два числа, например, 7 и 103. Так как K-1(n) = (n – 1)/2, то K-1(7) = 3 и K-1(103) = 51. Числу 3 соответствует двойка бубей, а числу 51 – туз бубей. Вот моя рука на префлопе!
-Здорово! То есть, нет, не очень... Если мы провернем такую операцию два раза – для тебя и для меня, – то получится, что нам сдают карты из разных колод! Вдруг мы сдадим друг другу одни и те же карты? Не годится! Колода должна быть одна.
-Да, ты права. Хорошо, давай колода будет моей, то есть ты сдаешь мне две карты точно так же, как и раньше. Вычеркнем из множества {K(1), K(2), ... , K(52)} два названных тобой числа, соответствующих моим картам. В нашем примере этими числами являются 7 и 103, то есть K(3) и K(51). Останется 50 чисел. Теперь надо сдать две карты тебе. Это проблематично, потому что, во-первых, тебе неизвестна функция K(n), и значит, ты не сможешь сдать себе карты сама, а, во-вторых, я не должен знать твои карты, поэтому я не смогу сдать карты тебе.
-Так-так-так... Мне кажется, что эти две проблемы можно решить. Ведь я тоже могу закодировать оставшиеся 50 карт и предоставить тебе выбор двух карт для меня. Я выберу кодирующую функцию J(n), которая будет известна только мне, вычислю 50 чисел J(K(1)),..., J(K(52)) (за исключением J(K(3)) и J(K(51))) и сообщу эти числа тебе. Поскольку ты знаешь функцию K(n), то ты сможешь легко получить из чисел вида J(K(n)) числа вида J(n).
-Не совсем так. Я смогу вычислить значения J(1),...,J(52), применив свою декодирующую функцию K-1(n), только в том случае, если J(K(n)) = K(J(n)) для любого n от 1 до 52. Другими словами, наши с тобой кодирующие функции K(n) и J(n) должны быть коммутативны относительно операции суперпозиции (подстановки друг в друга). Если это условие выполняется, то по твоим 50 числам вида J(K(n)) я определю 50 чисел вида K-1(J(K(n))) = K-1(K(J(n))) = J(n). Заметь, что я не знаю твою функцию J(n), поэтому я не знаю, какие карты скрываются за каждым из 50 чисел J(1), J(2), J(4), ..., J(50), J(52). Тогда я смогу произвольным образом вытащить из этого множества любые два числа, например J(1) и J(4), и назвать эти два числа тебе. Так как ты знаешь свою кодирующую функцию J(n), то, применив декодирующую функцию J-1(n), ты обнаружишь, что я выбрал для тебя карты под номерами J-1(J(1)) = 1 и J-1(J(4)) = 4, то есть двойку пик и двойку червей. С префлопом мы разобрались!
-Подожди, есть еще одна проблема. Мы загадываем K(n) и J(n) втайне друг от друга. Как решить проблему с коммутативностью наших кодирующих функций? Далеко не любые две функции обладают этим свойством.
-А что если мы будем выбирать кодирующие функции только определенного вида? Например, класс функций AI(n) = n·10I (I – натуральное) таков, что для любых натуральных K и J функции K(n) = n·10K и J(n) = n·10J коммутативны относительно суперпозиции, так как J(K(n)) = n·10K ·10J = K(J(n)).
-Супер! Итак, перед началом игры мы вместе тобой выбираем семейство коммутативных кодирующих функций, а потом каждый из нас втайне выбирает закрытый ключ – одну функцию из этого семейства. Проворачиваем наш алгоритм и... всё, карты на префлопе розданы! Определить флоп, терн и ривер еще проще, так как эти карты не нужно ни от кого скрывать! Кажется, мы почти готовы сыграть первую раздачу!
-Лен, знаешь о чем я подумал? Функции из семейства AI(n) на самом деле плохие. Вот представь: я называю тебе в качестве чисел K(1), K(2), ... , K(52) следующие числа: 10000000, 20000000, 30000000, ... , 520000000. Зная, что моя кодирующая функция имеет вид n·10I, ты моментально вычислишь мой закрытый ключ: K = 7, K(n) = n·107. После этого ты сможешь сдать мне любые карты по твоему выбору!
-Значит, нужно выбирать такое семейство AI(n), чтобы по числу n (от 1 до 52) и коду K(n) было бы невозможно расшифровать закрытый ключ К за обозримое время с помощью вычислительных методов.
-Именно! Если мы договоримся перед игрой выбирать кодирующие функции из семейства AI(n) = nK, то по числу 506623120463 ты вряд ли быстро определишь, что это есть ни что иное, как 477. Такое кодирование уже достаточно тяжело взломать. Следовательно, можно быть уверенным в том, что соперник не знает твоих карт.
-А что делать, например, с числами вида 10K? Увидев число, оканчивающееся на несколько нулей, я сразу получу некоторую информацию относительно закодированной карты, а именно, это будет одна из следующих карт: 10, 20, 30, 40, 50.
-Это хорошее замечание! Получается, что первоначальная нумерация карт числами от 1 до 52 не совместима с кодирующими функциями вида AI(n) = nK. Нужно нумеровать карты так, чтобы никакое свойство первоначальной нумерации карт не сохранялось после их кодирования. В частности, не должно сохраняться упомянутое тобой свойство числа оканчиваться на ноль.
-Петь, позволь один нескромный вопрос. Скажи, а я могу быть на 100% уверена в тебе?
-Хех, это ты к чему?!
-Я первая спросила, не уходи от ответа.
-Ну, не знаю... В принципе, да.
-Так “да” или только “в принципе”?
-Лен, что происходит? Что за допрос ты мне устраиваешь?
-Не горячись Smile Мне пришла в голову одна мысль. Скажи, а ты уверен, что у нас уже в первой раздаче не случится префлоп олл-ин АА против АА?
-Это очень маловероятно... Если, конечно, мы играем честно.
-Вот! Можно ли мне быть уверенной в том, что ты не сжульничаешь, выдав свои A2 за пару тузов?
-Для корректности покера в уме нам надо не полагаться друг на друга, а обеспечить механизм честной игры. Например, можно обязать нас с тобой после каждой раздачи, закончившейся шоудауном, рассекречивать свой закрытый ключ. Это позволит проверить, соответствуют ли названные нами на шоудауне карты тем, которые были розданы в действительности.
-Но я могу обмануть тебя, назвав другой закрытый ключ, соответствующий двум тузам.
-Надо сделать так, чтобы ты не смогла быстро подобрать ключ, соответствующий двум тузам. Появляется еще одно необходимое условие на семейство кодирующих функций AI(n): для любых ni и nl из начальной нумерации карт числами n1 ,..., n52 невозможно за обозримое время подобрать с помощью вычислительных методов два ключа K и J, такие, что K(ni) = J(nl).
-Честно говоря, я уже начинаю немного запутываться. Давай аккуратно опишем алгоритм покера вслепую.
-Нет проблем! Итак, вот очередность наших действий:
1) мы с тобой договариваемся относительно начальной нумерации всех 52 карт числами n1 ,..., n52;
2) мы с тобой договариваемся относительно семейства кодирующих функций AI(n);
3) я выбираю свой закрытый ключ K – функцию K(n) из семейства AI(n);
4) я вычисляю значения K(n1), ... , K(n52) и сообщаю их тебе;
5) ты выбираешь произвольным образом для меня два числа из множества чисел {K(n1), ... , K(n52)};
6) я декодирую эти два числа с помощью функции K-1(n) и узнаю свои две карты;
7) ты выбираешь свой закрытый ключ J – функцию J(n) из семейства AI(n);
Cool ты вычисляешь значения выражений вида J(K(nl)) для 50 оставшихся карт и сообщаешь их мне;
9) я с помощью функции K-1(n) вычисляю 50 значений выражений вида J(nl);
10) я выбираю произвольным образом два числа из этих 50 чисел и сообщаю их тебе;
11) ты декодируешь эти два числа с помощью функции J-1(n) и узнаешь свои две карты;
12) раунд торговли на префлопе.
Если игра продолжается дальше, то:
13) я выбираю произвольным образом три числа из оставшихся 48 чисел вида J(nl) и сообщаю их тебе;
14) ты декодируешь эти три числа с помощью функции J-1(n) и сообщаешь их мне, мы узнаем флоп;
15) раунд торговли на флопе;
Если игра продолжается дальше, то:
16) я выбираю произвольным образом одно число из оставихся 45 чисел вида J(nl) и сообщаю его тебе;
17) ты декодируешь это число с помощью функции J-1(n) и сообщаешь его мне, мы узнаем терн;
1Cool раунд торговли на терне;
Если игра продолжается дальше, то:
19) я выбираю произвольным образом одно число из оставихся 44 чисел вида J(nl) и сообщаю его тебе;
20) ты декодируешь это число с помощью функции J-1(n) и сообщаешь его мне, мы узнаем ривер;
21) раунд торговли на ривере;
Если игра доходит до шоудауна, то:
22) каждый из нас объявляет свои две карты;
23) определяется победитель раздачи, он забирает банк;
24) каждый из нас сообщает свой закрытый ключ для проверки честности игры.
-Хорошо, структура игры теперь понятна. Остается вопрос технического характера, но без ответа на него у нас с тобой все равно ничего не получится: как следует выбирать начальную нумерацию карт и семейство кодирующих функций AI(n), чтобы они удовлетворяли всем необходимым требованиям? Давай вкратце напомню все полученные нами ограничения:
1) коммутативность функций AI(n);
2) отсутствие сохранения свойств начальной нумерации при кодировании;
3) невозможность быстрой расшифровки кода;
4) невозможность жульничества путем замены закрытого ключа.
У тебя есть идеи, как решать задачу выбора начальной нумерации карт и семейства кодирующих функций?
Петя не успел рассказать Лене свои мысли по этому поводу. Зажегся свет, и лифт поехал вверх настолько же неожиданно, насколько он остановился пару часов назад. Надо ли говорить, что ребята оставили свою увлекательную дискуссию до лучших времен, предпочтя расслабиться после сегодняшнего приключения.
Алгоритм для игры в покер вслепую был предложен в 1979 году исследователями в области криптографии Adi Shamir, Ronald Rivest и Leonard Adleman (Massachusetts Institute of Technology) в статье «Mental Poker». Ее рекомендуется прочитать всем желающим узнать ответ на последний вопрос Лены. А цель данной статьи – знакомство читателей с рядом проблем, которые возникают при попытке моделирования покера в уме, – будем считать достигнутой.
#7 KRIK 4070K @ 10.11.09 15:19 [пожаловаться]
боян Shocked
#8 nofocemparms @ 10.11.09 15:20 [пожаловаться]
Arrow
Ответить
Very Happy Smile Sad Surprised Shocked Confused Cool Laughing Mad Razz Embarassed Crying or Very sad Evil or Very Mad Twisted Evil Rolling Eyes Wink Exclamation Question Idea Arrow
Новая тема
Подписаться
События
Будущие турниры
15 ноя Тюмень (4)
15 ноя Тюмень (1)
Добавить турнир
Последние дневники
Вкусно жрать или на улицу... (74)
Microsoft 3.0 или 1.1 (13)
Подготовка к войне (103)
Юбилей (16)
Элитная война (265)
Элита гуляет 2 (296)
Го дота (37)
Случайные галереи
Do6PbIuЖyk: 364 атака!
edepko: Megan Fox
edepko:
Avenger!: кыся
Ищем авторов!
ProPlay.ru ищет новых авторов. Прочитайте "Памятку для авторов" и, если заинтересовались, пишите нам editor@proplay.ru
Реклама
игры драки играть
Раздел бесплатных драк: драки на flash, мини драки, флеш игры онлайн, бесплатно
playground.ru/flash/ — Москва
игра Teenage Mutant Ninja Turtles: Video Game
Игровой портал PlayGround.ru: прохождение игр, коды, обзоры, новости.
playground.ru — Москва
мод для Cossacks 2: Napoleon Wars
Обзоры игр, описания, прохождения, моды, чит-коды и другие секреты.
playground.ru — Москва
скачать GTA San Andreas
Игровой сервер GTA.ru - игра по сети, описания, чит-коды и другие секреты
gta.ru — Москва
Идёт финал Народного Голосования Премии Рунета. Поддержите нас!
Теперь не нужно подтверждать свой голос по почте!
Также, если кто ещё не видел — наш новый проект zadolba.li посвящён историям из жизни по ту сторону прилавка. Рекомендуем!
LJ-сообщество
Утверждено: 22945 В рассмотрении: 1477 Утверждено сегодня: 10
Страницы:459458457456…1>>
спрятать цитаты с отрицательным рейтингом
405011 [ + ... ] [:||||:] утверждена 2009-11-10 в 10:45
Алек: Скорее добрый вечер!
Кот: А вот и Алек, по сто раз в скайп-чат скакалик
Кот: Алек, зачем вы вчера весь день скакали в чат и обратно?
Алек: против
Алек: у меня йота на ноуте и скайп автоматический
Алек: может быть он там скакал?
Кот: А, значит вы крышку открывали и закрывали?
Кот: вы там что, с помощью ноута вафли пекли?
405010 [ + 1286 ] [:||||:] утверждена 2009-11-10 в 10:13
xxx: на черно-белую пленку хорошо фоткается голая натура
xxx: если она, конечно, согласна
405009 [ + 1405 ] [:||||:] утверждена 2009-11-10 в 09:45
xxx: работаю в дурдоме
yyy: расказывай
xxx: мы с серёгой сидим в отдельном кабинете, кодим потихоньку, никого не трогаем. а в соседнем, сидят новенькие, человек пять. от нас к ним дверь напрямую и никогда не закрыта, они к нам постоянно бегают советоваться.
xxx: щас среди тишины из кабинета новеньких дикий крик "Великим докам по Java API, тройное ура!!!" и тут же хором "Ура! Ура! Ура!" и снова тишина
405008 [ + 1840 ] [:||||:] утверждена 2009-11-10 в 09:45
*** KABAN сменил имя на Оленька.
123: :-D
Оленька: чего смешного?
Оленька: я его жена
405007 [ + 2228 ] [:||||:] утверждена 2009-11-10 в 09:13
блин. все спрашивают, что мне подарить на др, а потом обижаются за то, что я им прямо говорю...
люди думают, что ты попросишь гель для душа
Не ходил на учебу полгода, перед сессией решил забежать.
В итоге узнал, что меня уже отчислили, у метро встретился с патрулем и получил повестку в военкомат. ПМП.
Кажется, что жизнь повернулась спиной? Поверьте, бывает и хуже: killmepls.ru
Все на скачку! Беспрецедентная раздача ключей для скачивания лицензионного софта от Microsoft для студентов: Visual Studio 2008, Windows Server 2008 R2, Expression Studio 3, SQL Server 2008 и другие — бесплатно!
405006 [ + 1698 ] [:||||:] утверждена 2009-11-10 в 09:12
xxx: У меня расстройство желудка
xxx: Он расстроен, что я его не кормлю )
405005 [ + 2101 ] [:||||:] утверждена 2009-11-10 в 08:45
xxx: как показывает опыт, лучшее средство для профилактики гриппа - искренне желание им заболеть
405004 [ + 2181 ] [:||||:] утверждена 2009-11-10 в 08:45
xxx: а в Испании есть город Сон-Сервера. Тихий, наверное, городок )
405003 [ + 4027 ] [:||||:] утверждена 2009-11-10 в 08:13
RDT:
аха, круто писать девке, что маленький, лысый и толстый но есть инфинити и слышать от неё, что главное - не внешность, а душа )
405002 [ + 2613 ] [:||||:] утверждена 2009-11-10 в 08:12
Из ВиО Google
Yippo: Насколько быстрее изнашивается карбюраторный двигатель, если зимой заводить машину и сразу ехать на "подсосе"?
Yippo: Можно ли так делать вообще?
TimXX: Я так пробовал. Движка хватило на три дня.
TimXX: Два дня нормально вроде ездил, а на третий мне в морду самосвал въехал, движку хана...(
405001 [ + 10323 ] [:||||:] утверждена 2009-11-09 в 10:11
Крик души в социальной сети:
ххх> Достали малолетки!!! Где же вы, взрослые парни 13-ти лет?!?!
405000 [ + 3331 ] [:||||:] утверждена 2009-11-09 в 09:45
он: Ээй! ты что, спать пошла? А как же эротическая беседа?.. )
она: я тебе сейчас только мозг проебать смогу...
она: сойдет за эротику?
404999 [ + 10671 ] [:||||:] утверждена 2009-11-09 в 09:45
xxx: Аня, у тебя есть сиськи?
yyy: Да! Больше чем у Семенович!
xxx: Три?
404998 [ + 2943 ] [:||||:] утверждена 2009-11-09 в 09:12
Речь идёт о домашних полозах (змеи которые).
xxx: Ну это да. Особенно самец хорош. Красавчег такой себе...
xxx: Крышку забудешь закрыть, потом из трубы пылесоса приходится 20 минут выманивать
404997 [ + ... ] [:||||:] утверждена 2009-11-09 в 09:11
xxx: Слушай, ну я понимаю чем отличается наше новое поколение от старого, а чем отличаются иностранные?
yyy: Да собственно тем же, только у них к тому ещё новое поколение смотрит стар варс 1-3 эпизоды, а старое 4-6 эпизоды.
404996 [ + 5237 ] [:||||:] утверждена 2009-11-09 в 09:11
ххх: а вообще, Саша, хоть и говно, но если копнуть поглубже, откроется очень умный, образованный, всесторонне развитый человек с богатым внутренним миром.
ххх: только кто ж будет в говне копаться, кроме как по пьяни?
404995 [ + 6382 ] [:||||:] утверждена 2009-11-09 в 08:46
xxx: Ну и сколько ты зарабатываешь?
yyy: Зато нихера не делаю!
404994 [ + 6796 ] [:||||:] утверждена 2009-11-09 в 08:12
она: блин, я уже так хочу утро завтрашнего дня
он: а что будет завтра утром?
она: завтра утром я проснусь в 6 утра от будильника
он: нахрена, завтра же суббота!
она: выключу его нафиг, перевернусь на другой бок и снова усну до 12 часов
она: такооооой каааайф!
404993 [ + 2258 ] [:||||:] утверждена 2009-11-09 в 08:11
death: а чё не спал-то?
Lokki-Navigator: Зачет по практике предварительный
death: молился?
404992 [ + 5030 ] [:||||:] утверждена 2009-11-09 в 08:11
gregst: а еще раньше дворники с лобовухи снимали и с собой уносили, что б не украли, а сейчас перестали
badlogin: мой дед до сих пор зеркала снимает
TakHaDo: и как, прибыльно?
404991 [ + 8061 ] [:||||:] утверждена 2009-11-08 в 09:11
ххх: что ты делаешь, когда тебе нечего сказать человеку?
yyy: молчу
404990 [ + 2068 ] [:||||:] утверждена 2009-11-08 в 08:45
xxx: чтобы курицы всем хватало, надо чтобы у нее было четыре лапы
xxx: все равно не летает!
404989 [ + 2564 ] [:||||:] утверждена 2009-11-08 в 08:44
xxx: я так расчихалась, что, когда прекратила, чуть не уснула от облегчения
404988 [ + 7238 ] [:||||:] утверждена 2009-11-08 в 08:44
xxx: привет )
yyy: привет )
xxx: нужна твоя помощь?
yyy: нет )
404987 [ + 9366 ] [:||||:] утверждена 2009-11-08 в 08:13
ххх: Я ненавижу, когда ты куришь...
ууу: А я ненавижу, когда ты на компе играешь!
ххх: Ну согласись, когда я подхожу к тебе, от меня сталкером не воняет!
404986 [ + 8224 ] [:||||:] утверждена 2009-11-07 в 08:44
Metis: Старею. 22 года, а такие залысины, волосы выпадают. Вот скажи, куда они деваются?
NINZO: в носу посмотри
Metis: сволочь!!!
404985 [ + 12709 ] [:||||:] утверждена 2009-11-07 в 08:44
XXX: Мля. Эпидемии, пираты.
YYY: средневековье, мать его
404984 [ + 11029 ] [:||||:] утверждена 2009-11-07 в 08:12
она: очень красивая авка! А это ты на фоне чиго?
он: Это Кремль. Ты когда-нибудь была в Москве?
она: неа, а ты?
404983 [ + 8749 ] [:||||:] утверждена 2009-11-07 в 08:12
xxx: только когда количество компьютеров равно количеству членов семьи, в семье возникает полное взаимопонимание
404982 [ + 1816 ] [:||||:] утверждена 2009-11-07 в 08:11
xxx: А вот мой племянник уверен, что сюжет известной русской сказки замешан на том факте, что принцессу Василису во время экскурсии по лаборатории укусила генномодифицированная радиоактивная лягушка...
404981 [ + 14726 ] [:||||:] утверждена 2009-11-06 в 10:12
ууу : Какие люди! Год тебя в аське не видел.
ххх : Извини, случайно удалил тебя из списка невидящих, сейчас исправим ;-)
404980 [ + 2131 ] [:||||:] утверждена 2009-11-06 в 09:45
xxx: Нужно закрыть свое ИП, кто закрывал, расскажите с чего начать?
yyy: Идешь в налоговую, там тебя банят по ИП
404979 [ + 2994 ] [:||||:] утверждена 2009-11-06 в 09:45
[artemlight] (03:35:54) ща тут с друганом болтали о неврозах навязчивых состояний)
[artemlight] (03:36:00) в общем, нам нужно лечиться
[artemlight] (03:36:32) даже не знаю, почему. То ли потому, что мне ночью всякая фигня мерещится, а он на трещины в асфальте не наступает
[artemlight] (03:36:46) То ли потому, что мы в половине четвертого ночи болтаем о неврозах навязчивых состояний
404978 [ + 12936 ] [:||||:] утверждена 2009-11-06 в 09:12
Мать моя: У тебя есть арлекин?
я: Что?
Мать: Ну, арлекин, на компьютере?
я: В смысле?
мать: Программа такая.
я: Акробат?
мать: Да, акробат.
404977 [ + 7528 ] [:||||:] утверждена 2009-11-06 в 09:11
xxx: Ага, самая популярная мужская отмаза в настоящее время
xxx: "Да неее, я это не смотрю. Мне так, чисто рейтинг на торренте поднять и всё!"
404976 [ + 8373 ] [:||||:] утверждена 2009-11-06 в 09:11
ххх: Бывают девушки - ну чистый ангел, воплощение красоты, скромности и добродетели. Пока рот не откроют.
ууу: Что кариес?
ххх: Ага, кариес мозга
404975 [ + 5696 ] [:||||:] утверждена 2009-11-06 в 08:46
xxx: Мне надоело готовить себе ужин. мне надоело убирать свою квартиру. мне надоело просыпаться по будильнику. мне вообще надоело жить одной.
yyy: тебе в армию надо, там ни одной из этих проблем нет
404974 [ + 3884 ] [:||||:] утверждена 2009-11-06 в 08:45
Nazar: не болеете?
Nazar: на работе никто не чихает?
Alexey: Все чихают на работу
404973 [ + 11197 ] [:||||:] утверждена 2009-11-06 в 08:13
==Artes==: слушай, я тебе фотку вышлю, сделай меня в фотошопе лысым, пожалуйста.
FATALITY: нафиг?
==Artes==: да вот интересно просто, у меня есть родимое пятно под волосами или нет...
404972 [ + 7546 ] [:||||:] утверждена 2009-11-06 в 08:12
KiloBaks: специальная игра, пойми на что девушка обиделась, и обьясни ей )
KiloBaks: попыток нет, жизнь одна
404971 [ + 5964 ] [:||||:] утверждена 2009-11-05 в 09:46
No_Future: в таможке крутая методичка по информатике
No_Future: лаба "графический редактор Pain"
404970 [ + 2273 ] [:||||:] утверждена 2009-11-05 в 09:12
вот что мне интересно
магазин спального белья - Спал Спалыч
а как бы назывался магазин сантехники от этих креативщиков?
404969 [ + 4706 ] [:||||:] утверждена 2009-11-05 в 09:11
xxx: а у меня запах тройного одеколона навсегда проассоциирован с советской магнитофонной техникой
404968 [ + 3322 ] [:||||:] утверждена 2009-11-05 в 09:11
она: Дорогой, ну пусть во мне будет хоть несколько месяцев, какая-то загадка...
он: Несколько месяцев держится загадка, если пара не хочет делать узи для определения пола! )
404967 [ + 5420 ] [:||||:] утверждена 2009-11-05 в 08:46
Дракула: у кого есть стратегия линейка
DeBugger: Дракула> У меня есть экшн-транспортир. Надо?
404965 [ + 3545 ] [:||||:] утверждена 2009-11-05 в 08:44
xxx: Здесь есть люди, которые могут долго представлять себе бесконечность вселенной? )
yyy: Есть. Могут. Но страшно
404964 [ + 12234 ] [:||||:] утверждена 2009-11-05 в 08:13
xxx: Саню недавно из реанимации выписали. Он теперь курить бросил и в ветреную погоду дома сидит
yyy: А что случилось?
xxx: Он курил на остановке ночью, дул сильный ветер. Рядом проходила кучка гопов. Ну он кинул бычок в урну, а попал в реанимацию...
404963 [ + 9328 ] [:||||:] утверждена 2009-11-05 в 08:11
Jekyll:
Какие у нас безобидные названия...
Ракеты "Тополь". Ща сказали о успешном запуске с подводной лодки межконтинентальной баллистической ракета "Синева"!
Serenkiy Iozhik:
так вот что значит выражение "озарило синевой"...
Нужна еще противопехотная мина "Незабудка"
Serenkiy Iozhik:
поле было усыпано незабудками... поэтично
404962 [ + 4208 ] [:||||:] утверждена 2009-11-05 в 08:11
Raus: Счастья кругом - сколько угодно. Только нагибайся и подбирай.
АллекС: Вот уж действительно - каждому своё!
404961 [ + 10031 ] [:||||:] утверждена 2009-11-04 в 09:12
MorpheuS: революция какого числа?
Lexx: 7 ноября
MorpheuS: в царское время за такую переписку нас бы сослали в Сибирь
Страницы:459458457456…1>>
Мне пришла в голову одна мысль. Скажи, а ты уверен, что у нас уже в первой раздаче не случится префлоп олл-ин АА против АА?
ты вычисляешь значения выражений вида J(K(nl)) для 50 оставшихся карт и сообщаешь их мне;
