Читать «Число, пришедшее с холода. Когда математика становится приключением» онлайн - страница 61

Теперь нам ясно, как работают кудесники-шифровальщики. Правда, открытым остается еще один вопрос.

Большие простые числа

Что, однако, можем мы теперь спросить, помешает русским агентам посчитать результат так же, как считал его Тоби? Ведь они же знают, не хуже Цирка, модуль 221 и экспоненту 11, а также отправленное Джорджем Смайли кодовое число 184. Что мешает им вычислить остаток от деления числа 184³⁵ на 221?

Дело в том, что они не знают секретную экспоненту 35.

Но не могут ли они, зная модуль 221 и показатель степени 11, вычислить секретную экспоненту 35? Ведь каким-то образом это удалось сделать яйцеголовым из Цирка, которые затем заперли в сейф бумажку с этим заветным числом.

Надо сказать, что вообще-то это возможно. И нет никакой тайны в том, как именно получили число 35. Во всяком случае, ее нет, если знать, что 221 есть результат перемножения двух простых чисел 13 и 17: 13 × 17 = 221. Все остальное очень просто. Далее следуют такому «рецепту»: из обоих простых чисел вычитают по единице и получают соответственно числа 12 и 16, а затем перемножают их: 12 × 16 = 192. Это число 192 является «секретным модулем».

Затем составляют таблицу из увеличенных на единицу произведений последовательности натуральных чисел на секретный модуль 192, или, другими словами, следующие числа:

1 × 192 + 1 = 192 + 1 = 193,

2 × 192 + 1 = 384 + 1 = 385,

3 × 192 + 1 = 576 + 1 = 577,

4 × 192 + 1 = 768 + 1 = 769,

5 × 192 + 1 = 960 + 1 = 961

…

Какое-то из полученных чисел 193, 385, 577, 769, 961, … делится на показатель степени 11. В нашем примере уже второе из этих чисел кратно 11 — действительно, 385: 11 = 35. Так мы находим секретную экспоненту 35.

Однако если это так просто, то к чему все эти хлопоты? На самом деле все так просто, потому что в нашей вымышленной истории за модуль было принято небольшое число 221, которое можно без особых усилий представить в виде произведения двух простых чисел. Если бы Цирк предложил в качестве модуля большое число, то вся простота мгновенно бы улетучилась.

Здесь надо, конечно, признать, что вся история о Смайли и его требовании прислать агента 007 до предела упрощена, и вообще в реальности ничего подобного быть просто не могло. Хотя бы по той причине, что описанный мною способ шифрования был изобретен только в 1977 г. в Массачусетском технологическом институте. К этому времени Джордж Смайли уже давно был на долгожданном покое и, как писал Джон ле Карре, «поселился в Стипл-Астоне и жил так, как вышедший на пенсию старый чудак-отшельник, удивлявший обывателей своей милой привычкой бродить по улицам, вслух разговаривая с самим собой».