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

Доказанный здесь факт называют теоремой Ферма. Это не «большая теорема Ферма», о которой рассказывает Саймон Сингх в своей чудесной книжке «Великая теорема Ферма», а так называемая «малая теорема». Правда, эта теорема вовсе не «малая», скорее она очень даже значительная. Кстати сказать, Ферма ни словом не обмолвился, как он пришел к этой теореме. Только столетие спустя Леонард Эйлер смог доказать, почему эта теорема верна. Если известно, что a^p — a = a(a^{p — 1} — 1) делится на простое число p и если само число a на p не делится, то отсюда следует, что при делении a^{p — 1} на p необходимо получается остаток, равный единице, потому что если a не делится на p, то a^{p — 1} — 1 должно делиться на p. Это утверждение иногда тоже называют «малой теоремой Ферма».

Например, при делении двенадцатой степени любого, не делящегося на 13 числа получается остаток, равный единице. Или при делении шестнадцатой степени любого, не делящегося на 17 числа получается остаток, равный единице.

Здесь довольно неожиданно снова подходим к методу шифрования Джорджа Смайли: дело в том, что малая теорема Ферма гласит: для каждого, не делящегося на 13 числа a, в частности для a = 7 при делении числа a¹² на 13 получится остаток, равный единице. Малая теорема Ферма гласит также, что — в случае, если a не делится на 17, — шестнадцатая степень числа a¹², то есть число (a¹²)¹⁶ = a^12 × 16 = a¹⁹² делится на число 17 с остатком, равным единице. На 13 это же число тоже делится с остатком, равным единице. То есть при делении степени a¹⁹² на модуль 13 × 17 = 221 мы с гарантией получим остаток, равный единице. Запишем это в виде формулы: a¹⁹² ≡ 1.

Число 192, которое мы получили в результате следующего вычисления: (13 — 1) × (17 — 1) = 12 × 16, столь же секретно, как и извлеченный Тоби Эстерхази из сейфа секретный коэффициент 35. Назовем 192 «секретным модулем».

Умники из Цирка определили, с помощью секретного модуля 192, для степени 11 секретную экспоненту 35. Это число, 35, появляется в силу того, что для него справедливо равенство 35 × 11 = 1 + 2 × 192. Смайли отправил в Цирк из-за железного занавеса радиограмму с числом 184. Это был остаток, который при a = 7 получается от деления a¹¹ на число 221. В общем виде назовем остаток, который получается при делении a¹¹ на 221, кодированным, или зашифрованным, числом c. В нашем случае c = 184. Тоби Эстерхази вычисляет остаток от деления c³⁵ на 221, то есть числа (a¹¹)³⁵на 221. Тем самым он декодирует зашифрованное послание c, превращая его в исходное сообщение a. Почему?

Потому что в (a¹¹)³⁵ число a умножается само на себя 11 × 35 раз, что, в силу того что 35 × 11 = 1 + 2 × 192, означает, что число a суммарно 2 × 192 раз, а затем еще один раз умножается само на себя. Если 192 раза перемножить число a само на себя, после его деления на 221 получится остаток 1. Если то же самое сделать 2 × 192 раз, то получится тот же остаток 1, потому что 1 × 1 = 1. Если же этот остаток еще раз умножить на a, то в итоге получится остаток a × 1. Другими словами, остаток от деления c³⁵ на модуль 221 равен a × 1, то есть a. Поэтому Тоби, после вычисления остатка от деления 184³⁵ на 221, узнает о желании Смайли встретиться с агентом номер 7.