РАЗВЕДЧИКИ И ПОГРАНИЧНИКИ

[Аленка]

Теория чисел, некогда воспринимавшаяся как эзотерическая наука о загадочных свойствах простых чисел, самым неожиданным образом вторглась в современную криптографию. Большинство электронных платежей теперь осуществляется при помощи цифровой подписи, известной как алгоритм Райвеста-Шамира-Адлемана (Rivest-Shamir-Adleman) (RSA). В его основе лежит принцип разложения числа, представляющего собой результат перемножения двух простых чисел на множители.

 

Перемножение двух больших простых чисел есть не что иное, как односторонняя функция. Этот процесс занимает всего несколько микросекунд, а время, затраченное на выполнение данной операции, прямо пропорционально длине этого числа, отображенного в двоичной системе. Напротив, поиск двух простых множителей числа, скажем объемом в 512 бит, может занять несколько часов. Даже после того, как искомые величины будут найдены, перебор оставшихся вариантов продолжится. Для чисел в 2 048 бит подобный процесс считается нецелесообразным, поскольку он занимает практически неограниченно долгое время. Для защиты особо важной военной и промышленной информации используются более сложные способы криптографической защиты, при которых даже сверхбыстрый поиск оказывается неэффективным.

 

Это подводит нас к головоломке, придуманной Джоном Маккарти (John McCarthy), - автором языка программирования Lisp и теории искусственного интеллекта. В 50-х годах Майкл Рабин (Michael Rabin), известный изобретатель прикладных и развлекательных компьютерных программ, разгадал головоломку. Сумеете ли вы?

 

Задача формулируется следующим образом: группа разведчиков проникает на вражескую территорию. После выполнения задания бойцы возвращаются, но при переходе границы или их застрелят свои, приняв за шпионов, или пограничники пропустят вражеских агентов на свою территорию. Чтобы избежать недоразумений, каждый разведчик должен будет назвать свой пароль, который пограничник должен будет опознать. И разведчики, и пограничники вполне надежны, но вдруг они проболтаются за кружечкой пива в баре? Итак: какого рода информацию можно доверить пограничникам, и какие пароли должны называть разведчики, чтобы только они смогли пересечь границу, даже если пограничники выдадут известные им сведения? Подсказка - рассуждение о простых числах.

 

 

Денис Шаша

[Lexus43]

Подсказка - рассуждение о простых числах.Денис Шаша

Эх! Говорила мама:"Учи математику!"

[Жена Кума младшего]

Может сколько букв в его имени...

[Аленка]

Может сколько букв в его имени...

пограничники всё равно смогут спалить разведчиков..))))

[VOLK]

пограничники всех могут спалить!!!

[Аленка]

всех могут спалить!!!

)))) поэтому здесь и надо найти то решение, которое не позволит погранцам, как бы они не хотели - спалить разведчиков..))))

[Жена Кума младшего]

как бы они не хотели - спалить разведчиков..))))

Кодировка цифр имеет место быть?

[Аленка]

нет, кодировки нет.. простые операции с простыми числами..

[Жена Кума младшего]

простые операции с простыми числами..

Так, что там в математике есть: сложения, вычитания, умножения, деления....

[Аленка]

)))) вот всё тебе скажи..)))) там есть множение..)))))

[Жена Кума младшего]

там есть множение..)))))

Ага, значитьс надо применить знания и калькулятор. А у пограничников есть сей вычислительный прибор? Или они в уме это делают?

[Аленка]

А у пограничников есть сей вычислительный прибор? Или они в уме это делают?

есть, он находится в уме..)))))))

[Жена Кума младшего]

А почему только я думаю?...........у меня уже кипит.....

[Цепина]

А почему только я думаю?...........

Думают все! Но про себя...шепотом! ))) Не отсвечивая.... Задачки ты, Алёнка, задаёшь...))...мозг можно сломать!)

[Аленка]

Задачки ты, Алёнка, задаёшь...))...мозг можно сломать!)

Вы сильно удивитесь насколько прост ответ..)))))

[Жена Кума младшего]

Думают все! Но про себя...шепотом! ))) Не отсвечивая....

Так не честно: надо высказываться, и оставлять мысли вслух!!!!!Ну-ка математики, собирайся в круг!!!!!

[Аленка]

Ну што, всё никак????..))))) Хде отгадки, хде предположения????... Включайте мозг..))))

[Жена Кума младшего]

????... Включайте мозг..))))

Я включила::::: что-то ничего нет))))))Хотя вот: если возьмем два числа, умножим их между собой; получается итог. Его знает пограничник. А разведчик знает те начальные числа. По возвращению назад, разведчик называет свои числа, а пограничник их перемножает и сверяет свое число с полученным результатом.Как?

[Аленка]

Как?

отлично, молодэц!!..))) наконец-то отгадка нашла свою голову..))))) А ведь всё так просто, а??..))))Под каким кустом, во время дождя, прячутся пограничник с собакой???..))))

[Жена Кума младшего]

Под каким кустом, во время дождя, прячутся пограничник с собакой???..))))

Под мокрым))) и только собака)))

[Аленка]

Ночью, в полдень, на рассветеСлужбу он несет в секрете,На тропе, на берегу,Преграждая путь врагу....Я понимаю, всё тут очевидно и понятно, но всё же..)))))

[Жена Кума младшего]

Преграждая путь врагу....

Ха-ха...)))) Отряд пограничников!!!!!!!