Схемы криптографии

Криптография, грубо говоря, изучает вопросы, связанные с процессом коммуникации

• наличие которого ясно всем заинтересованным
• содержимое которого (в идеальном случае) узнать может только круг лиц, определённый участниками этой коммуникации

Не следует путать криптографию со стеганографией, которая изучает вопросы сокрытия самого факта коммуникации.

Настоящий курс посвящён именно элементам криптографии в вышеупомянутом смысле.

Симметричное и асимметричное шифрование

Симметричные схемы

Шифр Виженера

Одной из первых реально эффективных схем шифрования был шифр Виженера.

Устроен он следующим образом. Пусть Вася хочет иметь возможность общаться с Петей так, чтобы сообщения, которые они передают друг другу, никто посторонний не мог прочитать.

Они заранее встречаются и договриваются о неком «секрете»: для примера, пусть это будет слово «гриб».

Теперь Вася хочет передать Пете сообщение «укошкисемерокотят».

Для этого он циклически продолжает секрет: «грибгрибгриб…». После чего складывает своё сообщение с результатом такого продолжения, получая «».

Под сложением в данном случае понимается нечто наподобие:

def add_chars(x, y):
  return chr(ord('а') + (ord(x) + ord(y) - 2*ord('а')) % 32)
  ## 32 -- размер используемого алфавита (без буквы ё)

def add_messages(m1, m2):
  chars = [add_chars(m1[i], m2[i]) for i in range(len(m1))]

  return ''.join(chars)

В результате получается «цъцщншщжпхшпнюъах», что мало напоминает исходное сообщение (поскольку одни и те же символы в результате шифрования преобразуются в различные, полностью сбивается распределение частот символов).

Пете же для дешифровки достаточно вычесть из полученного им сообщения зацикленный секрет.

Шифр Виженера — одна из самых простых симметричных схем шифрования. Под симметричностью понимается наличие некого секрета, который используется как для шифрования, так и для дешифровки.

Шифр Фейстеля

Одна из реально используемых сейчас схем в упрощённом виде выглядит так:

• выбирается последовательность функций \(f_1, f_2, \ldots f_m\): каждая с \(N\) двоичными входами и таким же количеством двоичных выходов
• кодируемое сообщение каким-либо образом дополняется до длины \(2N\)
• пусть \(L_0\) и \(R_0\) — левая и правая половины входного сообщения соответственно
• вычисляется последовательность \(L_{n}=R_{n-1}\), \(R_{n}=L_{n-1}\oplus f_n(R_{n-1})\) (здесь \(\oplus\) — поразрядный XOR)

Декодировка осуществляется ровно так же, только функции используются в обратном порядке.

Эта схема называется шифром (или сетью) Фейстеля. Секретом является сама последовательность функций (на практике функции являются общеизвестными, но зависящими от неких параметров, набор которых является секретным).

Также отметим, что двоичные входы можно заменить на произвольные, а поразрядный XOR — на любую обратимую (не обязательно даже поразрядную) функцию.

Разбиение на блоки

Если сообщение достаточно длинное (длиннее тех частей ключа, которые определяют вышеупомянутые функции \(f_i\)), то его приходится разбивать на блоки.

Для того, чтобы одинаковые блоки после шифрования становились разными, каждый неким образом модифицируют. Самое частое (и простое): такой блок можно обратимым образом совокупить с элементом некоторой детерминированной последовательности (например, поразрядно проXORить блок с его номером).

Также можно присоединить к блоку некие случайные данные (которые после дешифровки можно отрезать): при этом результат шифрования окажется длиннее исходного сообщения.

Общие свойства

К достоинствам симметричных схем относят:

• возможность эффективной реализации (тех схем, которые используются в реальности)
• ограниченность круга лиц, владеющих хоть какой-то информацией о секрете, используемом для шифрования/дешифровки

Основным же недостатком является необходимость сторонам коммуникации сформировать общий для них секрет: зачастую у этих сторон нет возможности «встретиться наедине».

Обычно общий секрет формируется одним из двух способов:

• при помощи алгоритма Диффи-Хеллмана (или ему подобных)
• придумывается одним из участников и передаётся остальным при помощи асимметричной схемы шифрования

Формирование общего ключа

Мы вкратце опишем схему, по которой работает алгоритм Диффи-Хеллмана, а конкретные детали обсудим существенно позднее, после освоения соответствующей части математической теории.

Вася и Петя (открыто) договариваются об использовании некоторой функции F с двумя входами и следующими свойствами:

• композициональная коммутативность: \(F(F(x,a),b)=F(F(x,b),a)\)
• однонаправленность: задача определения по \(F(x,a)\) и \(x\) хотя бы одного подходящего \(a\) имеет высокую вычислительную сложность

Далее Вася и Петя (также открыто) выбирают \(x\). Вася загадывает некоторое \(a\), Петя загадывает некоторое \(b\).

Далее Вася сообщает Пете \(F(x,a)\), а Петя сообщает Васе \(F(x,b)\).

Теперь и Вася, и Петя могут вычислить \(F(F(x,a),b)=F(F(x,b),a)\), что и будет являться для них их общим секретом.

Асимметричные схемы

Шифрование

Асимметричные схемы шифрования работают следующим образом:

• есть секрет, называемый приватным ключом; он известен ровно одному участнику коммуникации
• есть публичный ключ, известный всем участникам

Шифрование осуществляется при помощи публичного ключа (то есть любой может отправить сообщение обладателю приватного ключа), а дешифровка — приватным.

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

Классическим асимметричным алгоритмом является RSA.

Цифровая подпись

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

• лицо, желающее подтверждать аутентичность своих сообщений (т.е. тот факт, что их автором является именно это лицо, а не кто-то другой), открыто объявляет публичный ключ
• затем каждое своё сообщение это лицо шифрует своим приватным ключом

Если нечто удалось расшифровать публичным ключом во что-то осмысленное, то с высокой вероятностью это нечто — сообщение, написанное тем самым вышеупомянутым лицом.

Отметим, что на практике из-за медлительности асимметричных схем используется чуть другая схема:

• к сообщению применяется некая общеизвестная однонаправленная (в том смысле, что для любого из её результатов затруднительно установить хотя бы один набор входов, дающий этот результат) функция
• результат этой функции в зашифрованном виде прикладывается к сообщению

Чтобы проверить аутентичность сообщения, достаточно публичным ключом расшифровать приложение, а потом применить вышеупомянутую функцию к сообщению и сравнить.

Хеширование и аутентификация

Хеширование

Хеш-функциями в информатике называются функции, получающие на вход данные произвольного размера и выдающие результат фиксированного размера.

Для хеш-функций, используемых в криптографии, характерна однонаправленность. Это означает, что для данного результата затруднительно подобрать входные данные, дающие такой результат.

Есть некоторое количество широкоиспользуемых хеш-функций: MD5, SHA-1, SHA-2, SHA-3 (перечислены в порядке возрастания «надёжности» — сложности подбора входных данных по результату) и некоторые другие.

На хешировании основаны две распространённые схемы цифровой подписи:

• симметричная («имитовставка», также именуемая кодом аутентификации сообщения или Message Authentication Code)
• асимметричная, которую мы кратко описали в предыдущем разделе и более подробно опишем в следующем

Аутентификация сообщений

Аутентификацией сообщения называется проверка этого сообщения на аутентичность: факт того, что проверяемое сообщение написано именно его автором, а не тем, кто выдаёт себя за этого автора.

Сейчас мы разберём классическую симметричную схему. Напомним, что этим термином называются схемы, в которых дешифровку (или, в нашем случае, — проверку аутентичности) может осуществлять лишь ограниченный круг лиц, наделённых секретным ключом.

При этом отметим, что чаще всего в аутентификации по симметричной схеме участвует вообще одно лицо — сам автор сообщения: это позволяет отдавать такое сообщение на хранение кому-то другому без боязни, что оно будет модифицировано.

Подпись

Для того, чтобы сделать сообщение аутентифицированым, его сопровождают подписью, которая в нашем случае называется кодом аутентификации сообщения.

Рассмотрим две часто используемые на практике схемы подписи:

• простая: сообщение соединяется с секретным ключом, после чего хешируется
• «HMAC» результат простой схемы опять соединяется с секретным ключом, после чего хешируется

Чаще всего простая схема достаточно адекватна. Классическая атака на эту схему основана на произвольности формата сообщения, но большинство сообщений, которые в реальности подписываются подобным образом, имеют строго заданный формат, устойчивый к подобным атакам (впрочем, известны реальные случаи успешного применения таких атак к форматированным сообщениям; связанные, правда, с неадекватностью процедуры проверки формата).

Более же сложная схема HMAC считается более надёжной и рекомендуется для применения в промышленных ситуациях вместо «простой».

Хранение паролей

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

При этом, для того, чтобы одинаковые пароли давали разные коды аутентификации, каждый пароль дополнительно модифицируется так называемой солью, которая выбирается случайным образом и хранится в паре с кодом аутентификации.

То есть, разница с обычной аутентификацией сообщения лишь в том, что сообщение собирается из двух частей:

• той, что хранится в базе данных пользователей (соль)
• той, что предоставляет сам пользователь (пароль)

В принципе, ничто не мешает, как и в классической схеме, отдать пользователю на хранение и соль вместе с кодом аутентификации, только вряд ли типичный пользователь типичного сервиса сможет всё это запомнить и правильно передать сервису при необходимости входа. А хранить это в файле часто оказывается не слишком надёжным решением (как и хранить пароль на листочке, приклеенном к монитору).

Цифровая подпись

С точки зрения задачи цифровой подписи — аутентификации сообщения — гораздо привлекательнее выглядят асимметричные схемы: в таких схемах любой может проверить аутентичность сообщения.

В частности, цифровая подпись по асимметричной схеме используется для:

• установления зашифрованного соединения с HTTP-сервером (подтверждая, что ответивший на запрос сервер действительно соответствует доменному имени, введённому пользователем в адресную строку браузера)
• электронных писем (подтверждая, что отправитель — это именно тот, чей адрес указан в качестве обратного)

Зашифрованное соединение обычно использует симметричную схему шифрования. А асимметричная схема используется для передачи ключа симметричной схемы. Подписывается при этом публичный ключ этой асимметричной схемы.

Подробнее:

• владелец сервера, привязанного к доменному имени foo.bar, хочет получить возможность устанавливать зашифрованные соединения с клиентами
• он генерирует пару ключей (публичный и приватный), которые затем будет использовать для получения от клиентов ключа симметричной схемы
• также он обращается к сертифицирующей организации с запросом на получение сертификата
• сертифицирующая организация проверяет, что доменное имя действительно соответствует тому серверу, с которого происходит запрос, после чего выдаёт сертификат — публичный ключ владельца сервера вместе с некоторой вспомогательной информацией (в том числе — о самой организации)
• сертификат подписывается приватным ключом сертифицирующей организации

Теперь каждый, кто доверяет сертифицирующей организации, доверяет и владельцу сертификата.

Цепочки сертификатов

В реальности тех организаций, которым доверяют, например, ОС и браузеры, не так много: несколько сотен.

Сертифицирующих организаций гораздо больше. Для обеспечения возможности их работы используется очень простая схема: конечный пользователь (владелец сервера) предоставляет клиенту не один (свой) сертификат, а цепочку сертификатов: сертификаты всех промежуточных организаций между ним и «корневой».

В общих чертах цепочка выглядит так (опуская дополнительную информацию):

• «конечный сертификат»: имя сервера, ключ сервера (К0), имя издателя (И1), подпись (ключом К1), метка о конечности сертификата (чтобы не было возможности продолжить цепочку)
• следующий сертификат: имя субъекта (И1), ключ субъекта (К1), имя издателя (И2), подпись (ключом К2)
• следующий сертификат: имя субъекта (И2), ключ субъекта (К2), имя издателя (И3), подпись (ключом К3)

и так далее до

• «корневой сертификат»: имя субъекта (Иn), ключ субъекта (Кn), имя издателя (Иn), подпись (ключом Kn)

Элементы теории кодирования

Основные понятия

Кодирование и декодирование

Шифрование и дешифровка являются частными случаями более общих понятий кодирования и декодирования.

Пусть \(X\) и \(Y\) — два произвольных множества. Будем называть пару отображений \(c:X\rightarrow Y\) и \(d:Y\rightarrow X\) кодированием и декодированием, если \(d(c(x)) = x\) для всех \(x\in X\).

Обычно, когда говорят о кодировании и декодировании, то считают множества \(X\) и \(Y\) не совсем произвольными: почти всегда эти множества — множества конечных последовательностей элементов каких-нибудь «алфавитов».

Поэтому далее мы будем считать, что \(X\) состоит из конечных последовательностей элементов множества \(A\), которое в дальнейшем мы будем называть словом «алфавит». А вот \(Y\) мы будем считать множеством конечных последовательностей элементов двухэлементного множества \(\{0, 1\}\).

Посимвольное кодирование

Будем говорить, что \(c\) — посимвольное преобразование, если для любого \(n\) и любой последовательности \(x_1 x_2\ldots x_n\) выполнено

\[ c(x_1 x_2 \ldots x_n) = c(x_1)c(x_2)\ldots c(x_n) \]

Если вдобавок ещё и существует преобразование \(d\) такое, что \(d(c(x))=x\) для всех \(x\in X\), то будем называть \(c\) посимвольным кодированием.

Есть хороший признак посимвольного кодирования, называемый префиксным свойством или условием Фано:

• для любых \(x_1\ne x_2\) последовательность \(c(x_1)\) не является началом последовательности \(c(x_2)\)

Посимвольное преобразование, обладающее префиксным свойством, является кодированием! Доказательство этого факта оставим читателю в качестве простого упражнения.

Оценки эффективности

Эффективность посимвольного кодирования

Под неэффективностью того или иного способа кодирования мы будем понимать среднестатистическую длину закодированного сообщения в пересчёте на один символ (чем короче результирующие кодировки — тем более эффективным мы будем считать такой способ кодирования).

Для посимвольного кодирования это — то же самое, что и среднестатистическая длина кода символа.

Например, если в алфавите всего три символа, а никаких статистических закономерностей между теми или иными символами сообщения не наблюдается, то приходится считать, что вероятность встретить любой из символов равна \(1/3\). Таким образом, если длины кодов символов равны \(L_1\), \(L_2\) и \(L_3\), неэффективность кодирования равна

\[ \frac{L_1 + L_2 + L_3}{3} \]

Например, для равномерного кодирования (длины всех кодов символов одинаковы и минимальны) эта неэффективность равна

\[ \frac{2+2+2}{3} = 2 \text{(бит на символ)} \]

В общем же случае, если вероятности возможных символов равны \(p_1, p_2, \ldots p_n\), а длины их кодов равны \(L_1, L_2, \ldots L_n\) соответственно, неэффективность посимвольного кодирования равна

\[ \sum_i p_i L_i = p_1 L_1 + p_2 L_2 + \ldots + p_n L_n \]

Очевидно, эта неэффективность не может быть слишком маленькой: среди длин не может быть более одного нуля, более двух единиц, более четырёх двоек и так далее. К сожалению, такой «наивный» подход

• во-первых, даёт очень грубую оценку
• во-вторых, плохо исследуется математическими методами

Поэтому мы сейчас займёмся его модификацией.

Кроссэнтропия

Обозначим \(q_i = 2^{-L_i}\). Тогда неэффективность кодирования примет вид

\[ -\sum_i p_i \log q_i \]

Формула такого вида называется кроссэнтропией наборов \(p_1, p_2, \ldots p_n\) и \(q_1, q_2, \ldots q_n\).

У кроссэнтропии есть замечательное свойство: её очень легко оценить снизу, если фиксировать сумму \(q_i\). Поэтому без лишних слов обозначим \(S = \sum_i q_i\) и докажем, что

\[ -\sum_i p_i \log q_i \geqslant -\sum_i p_i \log (Sp_i) \]

Правую часть нетрудно получить как единственную критическую точку кроссэнтропии, рассмотренной как зависимость от \(q_2, \ldots q_n\).

Это неравенство можно преобразовать к виду

\[ \sum_i p_i \log \left(\frac{q_i}{Sp_i}\right) \leqslant 0 \]

Но это — частный случай неравенства Йенсена. Говоря по-другому, это — тривиальное следствие обратной выпуклости логарифма (точка на хорде находится под точкой на графике):

\[ 0 = \log 1 = \log \left( \sum_i \frac{p_i q_i}{S p_i} \right) \]

Таким образом, мы доказали, что среднестатистическая длина символа не меньше, чем

\[ -\sum_i p_i \log (Sp_i) = -\sum_i p_i \log S -\sum_i p_i \log p_i = -\log S - \sum_i p_i \log p_i \]

Второе слагаемое в (самой) правой части называется энтропией набора \(p_1, p_2, \ldots p_n\).

Оценка эффективности префиксных кодировок

В общем случае \(S\) не превосходит \(\log n + 1\). Но для префиксных кодировок \(S\) не превосходит \(1\): если расположить коды слов в листьях бинарного дерева, пути в котором — эти самые коды (например, код 011 соответствует шагу влево от корня, затем двум шагам вправо), то сумма \(q_i\) для всех кодов в таком дереве равна полусумме таких сумм в поддеревьях корня. В дереве же высоты 0 такая сумма равна либо 0, либо 1. Поэтмоу в деревьях высоты 1 эта сумма не превосходит 1. И в деревьях высоты 2 — тоже. И так далее (формально это можно доказать, предположив, что неравенство нарушается, и рассмотрев минимальную высоту деревьев, для которой это неравенство нарушается).

Поэтому эффективность префиксной кодировки не может быть лучше энтропии набора вероятностей символов. Тем не менее, даже такая эффективность не достигается. Самой же эффективной среди префиксных кодировок является кодировка Хаффмана.

Кодировка Хаффмана

Сначала договоримся, что мы будем рассматривать только такие префиксные кодировки, в которых ни один из кодов символов нельзя укоротить (путём удаления какого-либо из бит) с сохранением префиксности. Далее будем называть такие кодировки несократимыми.

Нетрудно заметить, что если самая эффективная префиксная кодировка и существует, то она обязана быть несократимой. Также заметим, что несократимых кодировок конечное количество: длина кода символа в несократимой кодировке не может превосходить общее количество символов.

Значит, самая эффективная префиксная кодировка существует: чтобы её найти, достаточно перебрать все несократимые префиксные кодировки. Далее все самые эффективные кодировки (вообще говоря, обычно есть много кодировок с одной и той же эффективностью) мы будем для краткости называть оптимальными.

Теперь сформулируем и докажем (доказательства написаны курсивом) несколько полезных фактов про оптимальные кодировки.

• В оптимальной кодировке код самого редкого символа самый длинный. Если это не так (т.е. есть менее редкий символ с более длинным кодом), то можно поменять местами коды самого редкого символа и символа с самым длинным кодом. Эффективность кодировки повысится.
• В оптимальной кодировке второй по редкости символ должен иметь код той же длины, что и самый редкий. Если символов хотя бы два, то в любой несократимой кодировке у самого длинного кода есть «сосед», отличающийся лишь последним битом. Если же в оптимальной кодировке второй по редкости символ имеет не ту же длину кода, что и самый редкий, можно код этого символа обменять с соседом кода самого редкого. Такой обмен увеличивает эффективность и, тем самым, противоречит оптимальности.
• Среди оптимальных кодировок существует такая (назовём её особо оптимальной), в которой два самых редких символа имеют соседние (в том же смысле, что и в доказательстве предыдущего пунтка) коды. Выберем любую оптимальную кодировку и поменяем местами соседа кода самого редкого символа с кодом второго по редкости символа, получив таким образом искомую кодировку.
• Если заменить в алфавите два самых редких символа (назовём их \(\alpha\) и \(\beta\)) с вероятностями \(p\) и \(q\) на один (назовём его \(\mathfrak{M}\)) с вероятностью \((p+q)\), то оптимальная для полученного алфавита кодировка может быть превращена в оптимальную для исходного путём раздвоения кодового слова \(w\) символа \(\mathfrak{M}\) на кодовые слова \(w0\) и \(w1\) для символов \(\alpha\) и \(\beta\). Пусть полученная кодировка не оптимальна и имеет неэффективность, равную \(N\). Тогда рассмотрим особо оптимальную кодировку, в которой коды символов \(\alpha\) и \(\beta\) соседние. Заменим эти два кода на их общий префикс, а символы \(\alpha\) и \(\beta\) — на \(\mathfrak{M}\). Получим кодировку, неэффективность которой меньше \(N-(p+q)\). Осталось заметить, что неэффективность исходной кодировки была равна \(N-(p+q)\).

Многократно редуцируя алфавит подобным образом, получим алфавит из одного символа, для которого оптимальная кодировка — пустой код. Оптимальная кодировка для исходного алфавита может быть получена обратной цепочкой «раздвоений». Такая оптимальная кодировка называется кодировкой Хаффмана.

Про кодировку Хаффмана нужно понимать, что:

• она определена неоднозначно (так как «раздвоение» можно сделать двумя разными способами, да и вариантов того, какие два символа соединять, иногда доступно сразу несколько)
• могут быть кодировки с такой же эффективностью, отличающиеся от любой из кодировок Хаффмана

Эффективность произвольного кодирования

Если рассматривается произвольное кодирование, то аналогом средней длины кода символа является следующая величина, определённая для каждого целого неотрицательного \(N\):

\[ \frac{1}{N}\sum_i P_i L_i \]

где сумма берётся по всевозможным текстам длины \(N\), символом \(P_i\) обозначена вероятность возникновения \(i\)-го текста, а \(L_i\) — длина \(i\)-го текста.

Как и ранее, вводя обозначение \(Q_i=2^{-L_i}\), мы можем получить нижнюю теоретическую оценку на неэффективность кодирования сообщений длины \(N\):

\[ -\frac{\log\sum_i Q_i}{N} - \frac{\sum_i P_i \log P_i}{N} \]

В числителе первой дроби среди слагаемых под логарифмом не более одной единицы, не более двух половин, не более четырёх четвертей и так далее… Это означает, что если количество слагаемых не превосходит \(2^{k}-1\), то вся сумма не превосходит \(k\).

Слагаемых \(Q_i\) у нас \(n^N\). Поэтому

\[ \sum_i Q_i \leqslant \log (n^N + 1) \leqslant \log (2 n^N) \leqslant 1 + N \log n \leqslant 2 N \log n \]

А «средняя длина кода символа» не меньше чем

\[ -\frac{\log(2N\log n)}{N} - \frac{\sum_i P_i \log P_i}{N} \]

Учитывая, что

\[ \frac{\log (2N\log n)}{N} \rightarrow_N 0 \]

можно говорить о том, что нижняя теоретическая оценка на неэффективность кодирования (для достаточно длинных сообщений):

\[ -\frac{\sum_i P_i \log P_i}{N} \]

Если же хочется в целом оценить неэффективность кодировки, не выбирая конкретную длину сообщений, то можно вычислить так называемое среднее Чезаро последовательности нижних оценок

\[ B_N = -\frac{\log(2N\log n)}{N} - \frac{\sum_i P_i \log P_i}{N} \]

Под средним Чезаро бесконечной последовательности \(B\) понимается

\[ \lim_k \frac{B_1+B_2+\ldots+B_k}{k} \]

Опять же, если заменить последовательность \(B\) на последовательность

\[ C_N = - \frac{\sum_i P_i \log P_i}{N} \]

то среднее Чезаро не поменяется (это следует из того факта, что среднее Чезаро сходящейся последовательности равно пределу этой последовательности; доказательство этого факта оставляем читателю в качестве нетрудного упражнения).

Вообще говоря, во всех вышеприведённых рассуждениях мы предполагали, что длина сообщения заранее известна и не требует кодировки. Если это не так, то можно либо явно кодировать длину её двоичной записью, либо добавить к алфавиту один дополнительный символ, сигнализирующей о конце. Оба этих способа не меняют нижнюю теоретическую оценку. Для первого способа длина кода длины в пересчёте на один символ сообщения в пределе равна нулю. Для второго способа длины всех сообщений просто увеличиваются на 1 с сохранением того же набора вероятностей. Среднее Чезаро от такого преобразования не меняется (аккуратное доказательство оставим в качестве упражнения для читателя).

Аддитивность энтропии

В случае, когда вероятности появления очередной буквы не зависят от того, какие буквы были до неё, вероятность получить текст, состоящий из букв с вероятностями \(p_{i_1}, p_{i_2}, \ldots p_{i_n}\), равна

\[ p_{i_1} p_{i_2} \ldots p_{i_n} \]

Энтропия такого набора, оказывается, просто в \(n\) раз больше энтропии набора \(p_i\). Для того, чтобы это понять, первым делом раскроем логарифм произведения и во всех суммах, кроме первой, переименуем «связанные переменные»

\[ -\sum_{i_1i_2\ldots i_n} p_{i_1} p_{i_2} \ldots p_{i_n} \log p_{i_1} p_{i_2} \ldots p_{i_n} = -n \sum_{i_1i_2\ldots i_n} p_{i_1} p_{i_2} \ldots p_{i_n} \log p_{i_1} \]

Осталось заметить, что

\[ \sum_{i_2\ldots i_n} p_{i_2} \ldots p_{i_n} = (\sum_i p_i)^{n-1} = 1 \]

откуда сразу следует, что искомая энтропия равна

\[ -n \sum_i p_i \log p_i \]

В пересчёте на один символ это даёт в точности энтропию набора \(p_i\).

Зависимые вероятности

Важно понимать, что энтропия является теоретическим минимумом, если события «на \(i\)-м месте текста встретился такой-то символ алфавита» являются независимыми. В противном случае может быть всякое.

Например, можно гипотетически предствить, что в алфавите всего две буквы: после \(a\) всегда идёт \(b\), а после \(b\) — всегда \(a\). Тогда вероятности встречи символов равны \(1/2\), а энтропия равна \(1\) биту на символ. Но при этом в реальности любое сообщение фиксированной длины можно закодировать \(0\) битами (а если длина заранее неизвестна, то на кодировку длины, равной \(n\), достаточно \(\log n\) бит, что в пределе также даёт \(0\) бит на символ).

Диапазонная кодировка

Диапазонная (она же — арифметическая) кодировка — способ достичь теоретического минимума неэффективности.

Пусть требуется кодировать сообщения, вероятность \(i\)-го из которых равна \(P_i\). Для этого разобьём отрезок от \(0\) до \(1\) на участки с длинами \(P_i\).

Каждое сообщение будем кодировать двоичной записью дробной части любой из точек этого отрезка.

Нетрудно заметить, что для того, чтобы хотя бы одно число с \(k\) двоичными цифрами в дробной части гарантированно попало в любой отрезок длины \(P_i\), достаточно, чтобы

\[ 2^{-k} \leqslant P_i \]

В частности, можно выбрать все \(k\) так, чтобы длины кодов равнялись результатам округления вверх соответствующих логарифмов. Различные варианты арифметических кодировщиков как раз и отличаются друг от друга алгоритмами выбора конкретных точек внутри отрезков.

Если все сообщения имеют одну и ту же длину \(N\), то неэффективность такого кодирования не превышает

\[ \frac{\sum_i P_i (1 + \log P_i)}{N} = \frac{1}{N} + \frac{\sum_i P_i \log P_i}{N} \]

Учитывая, что первое слагаемое имеет нулевой предел (и, более того, даёт вклад не более 1 бита в общую длину сообщения), можно говорить о том, что арифметическая кодировка достигает нижней теоретической оценки на неэффективность кодирования — удельной (в пересчёте на один символ) энтропии вероятностного распределения текстов. Иногда по этой причине арифметическая кодировка называется энтропийной.

Элементы теории чисел

В основе большинства криптографических алгоритмов лежат некоторые элементы теории чисел. По большей части, те, которые касаются свойств арифметик остатков.

С их определения мы и начнём.

Арифметика по модулю

Начнём с двух главных определений.

Делимость

Целое число \(x\) делится на целое число \(y\) тогда и только тогда, когда существует целое \(z\), для которого \(x=yz\).

В частности:

• 2 делится на 1
• 5 делится на 5
• 5 не делится на 3
• 1 не делится на 2
• 0 делится на любое целое число
• в том числе, 0 делится на 0
• 1 делится только на 1 и на -1

В литературе часто используется обозначение \(x\,|\,y\) для высказывания «\(y\) делится на \(x\)». Это обозначение читают как «\(x\) делит \(y\)».

Сравнимость

Целые числа \(x\) и \(y\) сравнимы по модулю \(z\) тогда и только тогда, когда \((x-y)\) делится на \(z\).

Мы будем использовать обозначение \(x\equiv_z y\) или просто \(x\equiv y\), если понятно, о каком именно модуле (так называется то самое \(z\)) идёт речь.

Также мы не будем употреблять слово «модуль» в значении «абсолютная величина».

У сравнимости есть 5 свойств, следующих из её определения:

1. для любого \(x\) верно, что \(x\equiv x\) по любому модулю
2. если \(x\equiv_n y\), то \(y\equiv_n x\)
3. если \(x\equiv_n y\) и \(y\equiv_n z\), то \(x \equiv_n z\)
4. если \(x\equiv_n y\) и \(a\equiv_n b\), то \(x+a\equiv_n y+b\)
5. если \(x\equiv_n y\) и \(a\equiv_n b\), то \(xa\equiv_n yb\)

Последнее свойство доказывается не совсем тривиально: нужно ввести обозначения \(x=y+Xn\) и \(a=b+An\). После этого свойство становится тривиальным.

Эти свойства позволяют общаться со сравнениями почти так же, как и с обычными равенствами: заменять какие-то подформулы некоей формулы на сравнимые с ними, получая формулу, сравнимую с исходной. Единственное важное отличие: равенство позволяет так делать с любой формулой, а сравнимость — только с формулами, составленными при помощи сложения/вычитания/умножения (но, например, не деления и не возведения в степень).

Алгоритм Евклида

Мы будем говорить, что последовательность \(a\), содержащая хотя бы два элемента, построена при помощи алгоритма Евклида тогда и только тогда, когда \(a_{n+2}\equiv a_{n}\) по модулю \(a_{n+1}\) для любого допустимого \(n\).

Например, следующие последовательности построены при помощи алгоритма Евклида:

• 3, 42
• 3, 42, 3
• 3, 42, 45, -3, 0
• 8, 5, 3, 2, 1, 0, 1, 5, 6

Фундаментальное свойство алгоритма Евклида

Если последовательность \(a\) построена при помощи алгоритма Евклида, то множество общих делителей \(a_{n}\) и \(a_{n+1}\) совпадает с множеством общих делителей \(a_{n+1}\) и \(a_{n+2}\).

Это напрямую следует из (тривиально проверяемого) свойства: если \(d\) является делителем \(a\) и \(n\), причём \(a\equiv_{n} b\), то \(d\) является делителем \(b\).

Алгоритм Евклида для нахождения НОД

Поскольку наибольший общий делитель \(x\) и нуля равен абсолютной величине \(x\), то если алгоритм Евклида дал последовательность, содержащую ноль, по соседством с ним в этой последовательности стоит (с точностью до знака) НОД начальной пары чисел.

Обеспечить наличие нуля в такой последовательности весьма просто:

def gcd(a, b):
    while b != 0: a, b = b, a%b
    return abs(b)

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

Вообще говоря, для каждой пары \(a\) и \(b\), в которой \(a\) не делится на \(b\), существует ровно два числа \(x\), для которых выполнено одновременно

• \(|x| < |b|\)
• \(a\equiv_{b} x\)

Эти числа: остаток \(r\) от деления \(a\) на \(b\) и \(r-|b|\).

Более того, среди этих двух чисел хотя бы одно по абсолютной величине не превышает половину \(b\).

Поэтому правильный выбор следующего числа позволяет получить ноль за количество шагов, не превышающее логарифм второго из начальной пары элементов последовательности.

Более того, даже если выбирать следующее число как просто остаток (например, подобно вышеприведённой программе), асимптотическая сложность алгоритма останется той же: если \(r > |b|/2\), то \(|b|-r\) является остатком от деления \(b\) на \(r\). Поэтому мы при выборе «неправильного» числа потратим всего лишь один лишний шаг на каждый такой «неправильный» выбор.

Переопределение

Договоримся далее под алгоритмом Евклида понимать именно такой, который порождает последовательность, заканчивающуюся нулём.

Алгоритм Евклида для решения сравнений

Рассмотрим уравнение в целых числах (отностельно неизвестных \(x\) и \(y\))

\[ ax + by = c \]

Заметим сперва, что если НОД \(a\) и \(b\) не делит \(c\), то решений, очевидно, нет. А если делит, то на него можно сократить обе части.

Поэтому без ограничения общности считаем, что \(a\) и \(b\) взаимно просты (то есть их НОД равен 1).

Решить уравение \(ax+by=c\) — в точности то же самое, что найти все \(x\), удовлетворяющие сравнению

\[ ax \equiv_b c \]

Если к этому сравнению приписать всегда верное

\[ bx \equiv_b 0 \]

то к полученной паре сравнений можно применить алгоритм Евклида (сравнения можно складывать и вычитать, а, соответственно, и говорить о сравнимости (в аспекте делимости нацело) сравнений по модулю сравнения), приводящий к

\[ \pm\text{НОД}(a,b)x \equiv_b \ldots \]

Учитывая взаминою простоту \(a\) и \(b\), получаем необходимое условие на \(x\) вида «\(x\) сравним с чем-то».

Оказывается, это условие является ещё и достаточным: у уравнения \(ax + by = c\) обязано быть хотя бы одно решение.

Это доказывается тоже при помощи алгоритма Евклида, который нужно применить к равенствам

\[ \begin{aligned} a\cdot 1 + b\cdot 0 & = a \\ a\cdot 0 + b\cdot 1 & = b \end{aligned} \]

получив равенство вида

\[ a\cdot A + b\cdot B = \pm1 \]

которое затем остаётся умножить на \(c\) или \(-c\) в зависимости от знака правой части.

Итого

Мы доказали следующее:

• у уравнения \(ax + by = c\)
• и, что эквивалентно, у сравнения \(ax\equiv_b c\)

есть решение тогда и только тогда, когда \(c\) делится на НОД \(a\) и \(b\), причём это решение (в аспекте неизвестного \(x\)) единственно по модулю частного \(b\) и упомянутого НОД.

Если записывать единственность в аспекте обоих неизвестных, то решение имеет вид

\[ \begin{aligned} x & = A + (b/d)\cdot k \\ y & = B - (a/d)\cdot k \end{aligned} \]

где \(d\) — НОД \(a\) и \(b\), а \(k\) — произвольное целое число.

Китайская Теорема об Остатках

Системы сравнений

Рассмотрим систему из двух сравнений

\[ \begin{aligned} ax & \equiv_m A \\ bx & \equiv_n B \end{aligned} \]

Без ограничения общности можно считать \(a\) и \(b\) равными единице:

• если \(A\) делится на НОД \(a\) и \(m\), то всё три коэффициента сравнения можно на этот НОД сократить, получив эквивалентное сравнение
• если не делится, то сравнение не имеет решений

Пусть теперь \(d=\text{НОД}(m,n)\), причём \(m=dM\) и \(n=dN\). То есть наша система имеет вид

\[ \begin{aligned} x & \equiv_{dM} A \\ x & \equiv_{dN} B \end{aligned} \]

Решение этой системы — то же самое, что и решение системы уравнений

\[ \begin{aligned} x & = dMy + A \\ x & = dNz + B \end{aligned} \]

Следствием которых является уравнение

\[ d(My - Nz) = B-A \]

Если \(B-A\) не делится на \(d\), то это уравнение не решается, и, как следствие, исходная система сравнений не решается.

Если же \(B-A\) делится на \(d\), то такое уравнение решается, причём множество всех его решений имеет вид

\[ \begin{aligned} y & = Y + Nk \\ z & = Z + Mk \end{aligned} \]

для какой-то пары чисел \(Y\) и \(Z\), удовлетворяющей

\[ d(MY-NZ) = B-A \]

Более того, подстановка такого множества решений в исходную систему даёт

\[ \begin{aligned} x & = dMY + A + dMNk \\ x & = dNZ + B + dMNk \end{aligned} \]

Эти два равенства, как нетрудно заметить, одинаковы, поэтому полностью множество всех решений системы имеет вид

\[ \begin{aligned} x & = dMY + A + dMNk \\ y & = Y + Nk \\ z & = Z + Mk \end{aligned} \]

В итоге мы получили, что исходная система сравнений эквивалентна

\[ x \equiv_{dMN} dMY + A \]

Общая теорема

Пусть \(d=\text{НОД}(m,n)\), причём \(m=dM\) и \(n=dN\). Тогда система сравнений

\[ \begin{aligned} x & \equiv_m A \\ x & \equiv_n B \end{aligned} \]

имеет решение тогда и только тогда, когда \(A\equiv_d B\), причём это решение единственно по модулю \(dMN\) (или, что то же самое, — по модулю \(mn/d\)).

Китайская Теорема об Остатках

Китайской Теоремой об Остатках (далее КТО) называется частный случай вышесформулированной теоремы для \(d=1\). А именно, верно следующее.

Пусть \(m\) и \(n\) взаимно просты. Тогда система сравнений

\[ \begin{aligned} x & \equiv_m A \\ x & \equiv_n B \end{aligned} \]

имеет единственное по модулю \(mn\) решение, то есть эквивалентна одному сравнению вида

\[ x \equiv_{mn} C \]

Формула Эйлера

Формула Эйлера

Рассмотрим число \(N\geqslant 1\) и все числа в пределах от \(0\) до \(N-1\), взаимно простые с \(N\). Договоримся далее называть такие числа приведённой системой остатков.

Рассмотрим по модулю \(N\) произведение всех остатков приведённой системы:

\[ a_1 a_2 \ldots a_m \equiv_N ??? \]

Выберем произвольный остаток приведённой системы \(a\) и для каждого \(a_i\) выберем такой остаток приведённой системы \(A_i\), для которого выполнено

\[ a_i \equiv_N a A_i \]

Упражнение: поймите, почему для каждого \(i\) такой остаток существует и единственный.

Продолжим рассматривать произведение всех остатков приведённой системы:

\[ a_1 a_2 \ldots a_m \equiv_N (aA_1)(aA_2)\ldots (aA_m) \]

Воспользуемся коммутативностью и ассоциативностью умножения:

\[ a_1 a_2 \ldots a_m \equiv_N a^m A_1 A_2 \ldots A_m \]

Заметим, что все \(A_i\) различны. Поскольку их ровно столько же, сколько и всего остатков приведённой системы, то последовательность всех \(A_i\) является перестановкой последовательности всех \(a_i\).

То есть

\[ a_1 a_2 \ldots a_m \equiv_N a^m (a_1 a_2 \ldots a_m) \]

А учитывая взаимную простоту \(a_i\) и \(N\), получаем

\[ 1 \equiv_N a^m \]

Это сравнение называется формулой Эйлера, а \(m\) — значением функции Эйлера на числе \(N\).

Далее функцию Эйлера мы будем обозначать буквой \(\varphi\).

Итого: если \(a\) и \(N\) взаимно просты, то

\[ a^{\varphi(N)} \equiv_N 1 \]

Полезные следствия

Рассмотрим сравнение

\[ x^{a} \equiv_N A \]

Пусть при этом \(a\) взаимно просто с \(\varphi(N)\) и \(A\) взаимно просто с \(N\).

Допишем к этому сравнению формулу Эйлера (взаимная простота \(x\) и \(N\) следует из таковой для \(A\) и \(N\)):

\[ x^{\varphi(N)} \equiv_N 1 \]

К подобной паре сравнений можно применить мультипликативный алгоритм Евклида. Сейчас мы покажем, как такие сравнения «делить друг на друга с остатком».

Пусть имеется пара сравнений

\[ \begin{aligned} x^{a} & \equiv_N A \\ x^{b} & \equiv_N B \end{aligned} \]

причём \(a = bk + r\). Тогда

\[ x^{a} = (x^{b})^k \cdot x^r \equiv_N A^k x^r \]

То есть мы получили

\[ A^{k-1} x^r \equiv_N 1 \]

откуда можно получить сравнение вида \(x^r \equiv_N C\).

Алгоритм Евклида закончится на сравнении

\[ x \equiv_N \mathfrak{M} \]

Более того, правую часть легко выразить через исходные данные: вместо мультипликативного алгоритма Евклида можно было найти любое решение уравнения

\[ ay + \varphi(N)z = 1 \]

(более того, во многих случаях это ещё и эффективнее с вычислительной точки зрения).

Тогда \(\mathfrak{M} = A^{y}\).

Осталось заметить, что

\[ (A^{y})^a = A^{ay} = A^{ay}\cdot 1 \equiv_N A^{ay}\cdot A^{\varphi(N)z} = A^1 = A \]

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

PS Заметим, что именно на подобной схеме основан алгоритм RSA. В вышеиспользуемых обозначениях для двух простых различных чисел \(p\) и \(q\)

• публичным ключом является любое \(a\), взаимно простое с \(\varphi(pq)=(p-1)(q-1)\), и число \(N=pq\)
• приватным ключом является вычисленное по этому \(a\) число \(y\) и также \(N=pq\).
• что шифрование, что дешифровка — возведение в степень, равную первой компоненте пары, составляющей ключ, по модулю второй компоненты этой пары, то есть — по модулю \(N\).

Быстрое вычисление функции Эйлера

Начнём с того, что \(\varphi(1) = 1\) (среди чисел от \(0\) до \(0\) с единицей не взаимно прост этот самый ноль). Но это — бесполезный факт.

Если \(N\) — простое число, то, очевидно

\[ \varphi(N) = N-1 \]

поскольку среди чисел от \(0\) до \(N-1\) с \(N\) не взаимно прост только ноль.

Если \(N=p^k\), где \(p\) — простое число, то

\[ \varphi(N) = p^k - p^{k-1} \]

поскольку с \(p^k\) не взаимно просты числа, кратные \(p\), и только они.

Если же \(N=ab\), где \(a\) и \(b\) взаимно просты, то из КТО следует

\[ \varphi(a\cdot b) = \varphi(a)\cdot\varphi(b) \]

Чуть подробнее: сравнение \(x\equiv_{ab} m\) согласно КТО эквивалентно системе

\[ \begin{aligned} x & \equiv_a A \\ x & \equiv_b B \end{aligned} \]

Нетрудно при этом заметить, что \(m\) в таком соответствии взаимно просто с \(ab\) тогда и только тогда, когда \(A\) взаимно просто с \(a\) и \(B\) взаимно просто с \(b\).

Квадратные сравнения

Сейчас мы рассмотрим квадратные сравнения по простому нечётному модулю. Далее на протяжении всего раздела этот модуль мы будем обозначать буквой \(p\).

Поскольку \(p\) нечётный, то любое квадратное сравнение можно записать в виде

\[ x^2 + 2ax + c \equiv_p 0 \]

и заменой \(y=x+a\) привести к виду

\[ y^2 \equiv_p d \]

Поэтому без ограничения общности будем рассматривать задачу извлечения квадратного корня

\[ x^2 = a \]

Количество решений квадратного сравения

Если \(a\equiv_p 0\), то сравнение \(x^2 \equiv_p 0\) эквивалентно \(x\equiv_p 0\):

• если \(x\equiv_p 0\), то оба сравнения верны
• если \(x\) не кратно \(p\), то обе части первого сравнения можно на этот \(x\) сократить, получив второе сравнение и заодно — противоречие, из которого следует всё, что угодно

Если же \(a\) не кратно \(p\), то у сравнения либо 0 решений, либо 2: если \(X\) — какое-то решение, то сравнение можно переписать как

\[ x^2 \equiv_p X^2 \]

что эквивалентно

\[ (x-X)(x+X) \equiv_p 0 \]

откуда легко следует \(x\equiv_p \pm X\). Из-за того, что \(p\) нечётно, решения \(+X\) и \(-X\) различны.

Распределение точных квадратов

Будем говорить, что \(a\) является квадратным вычетом или точным квадратом по модулю \(p\), если \(a\) не кратно \(p\) и сравнение \(x^2\equiv_p a\) имеет решения.

Если мы возьмём все числа от \(1\) до \(p-1\) и каждое возведём в квадрат, то мы получим ровно \(\dfrac{p-1}{2}\) разных (по модулю \(p\)) результатов: каждый получен ровно два раза, как мы только что доказали.

Это означает, что ровно половина ненулевых остатков по модулю \(p\) являются точными квадратами.

Разрешимость квадратного сравнения

Формула Эйлера для простого \(p\) и \(x\), не кратного \(p\), имеет вид

\[ x^{p-1} \equiv_p 1 \]

(Кстати, в таком случае её называют малой теоремой Ферма.)

Поэтому, если

\[ a^{\frac{p-1}{2}} \not\equiv_p 1 \]

то сравнение \(x^2\equiv_p a\) не имеет решений.

Рассмотрим оставшийся случай

\[ a^{\frac{p-1}{2}} \equiv_p 1 \]

Все \(\dfrac{p-1}{2}\) точных квадратов относятся как раз к этому случаю. Более того, у сравнения

\[ y^k \equiv_p b \]

не может быть больше чем \(k\) различных решений, как мы несколько позже докажем. Поэтому ни один неквадрат в такую ситуацию не попадает.

Итого, при \(a\) не кратном \(p\) сравнимость \(a^{\frac{p-1}{2}}\) с единицей экивалентна разрешимости сравнения \(x^2 \equiv_p a\).

Замечание

Поскольку

\[ a^{p-1} - 1 = \left(a^{\frac{p-1}{2}}-1\right)\left(a^{\frac{p-1}{2}}+1\right) \]

то \(a^{\frac{p-1}{2}}\) при \(a\), не кратном \(p\), может быть сравнимо только с единицей или минус единицей.

Алгоритм Тонелли

Сейчас мы научимся решать квадратные сравнения.

Сперва заметим, что если \(p = 4k+3\), то \(x=a^{\frac{p+1}{4}}\) является решением сравнения \(x^2 \equiv_p a\), и никаких хитрых манипуляций производить не нужно.

Пусть \(p = 1 + q 2^s\), где \(q\) нечётно (а \(s>1\)).

Алгоритм Тонелли строит последовательность приближений к решению сравнения. Нулевое приближение определяется так:

\[ x_0 = a^{\frac{q+1}{2}} \]

Если \(a^q \equiv_p 1\), то \(x_0\) — решение. Если нет, то есть такой \(k\), что \(k\)-кратное возведение \(a^q\) в квадрат даст \(-1\):

• \(s\)-кратное возведение \(a^q\) в квадрат даёт единицу (согласно формуле Эйлера)
• единицу можно получить возведением в квадрат только из единицы и минус единицы

ВНИМАНИЕ это важнейшее соображение следует запомнить! Именно оно лежит в основе алгоритма быстрой генерации больших простых чисел.

Найдём теперь такой \(b_0\), что \(k\)-кратное возведение \(b_0^2\) в квадрат даст \(-1\) и выберем

\[ x_1 = b_0 x_0 \]

Заметим, что:

• \(x_1^2 \equiv_p (b_0^2 a^q) a\)
• \(k\)-кратное возведение \(b_0^2 a^q\) в квадрат даст 1

Поэтому либо \(b_0^2 a^q\) сравнимо с \(1\), либо же его нужно меньше чем \(k\) раз возводить в квадрат, чтобы получить минус единицу.

Итого на каждой итерации мы строим

\[ x_{m+1} = b_m x_m \]

выбирая \(b_m\) так, чтобы \(b_m^2\) для получения минус единицы нужно было бы столько же раз возводить в квадрат, сколько и

\[ (b_{m-1}b_{m-2}\ldots b_0)^2 a^q \]

Остался один маленький вопрос: а как искать \(b_i\)? Ответ, оказывается, очень прост: случайным образом найти любой неквадрат (их половина) \(z\). При возведении \(z^q\) в квадрат минус единицу даст лишь предпоследняя \((s-1)\)-я итерация. Поэтому среди результатов этих итераций мы всегда сможем отыскать нужную нам.

Дополнение: у многочлена не бывает много корней

Сейчас мы докажем, что у любого многочлена степени \(k\) не может быть больше \(k\) различных по модулю \(p\) корней.

Пусть это неверно, и есть многочлен, у которого корней больше, чем его степень.

Рассмотрим любой «плохой» многочлен \(Q\) с наименьшей (среди всевозможных «плохих») степенью, которую обозначим \(m\). Заметим сразу, что \(m\geqslant 1\).

Пусть \(Q(x_i)\equiv_p 0\) для всех \(i\) от \(0\) до \(m\). Тогда для всех \(i\) от \(1\) до \(m\) выполнено

\[ Q(x_i) - Q(x_0) \equiv_p 0 \]

Осталось заметить, что если

\[ Q = q_m x^m + \ldots + q_1 x + q_0 \]

то вышерассмотренные разности равны

\[ (x_i - x_0)\cdot ( q_m x_i^{m-1} + q_{m-1} x_0 x_i^{m-2} + \ldots ) \equiv_p 0 \]

откуда (в силу некратности \(p\) первых сомножителей левых частей) следует наличие у многочлена

\[ q_m x^{m-1} + q_{m-1} x_0 x^{m-2} + \ldots + q_1 x_0^{m-1} \]

не менее чем \(m\) различных решение, что противоречит предположению о минимальности \(m\).

PS Вообще говоря, доказать, что числа \(a\), для которых \((p-1)/2\)-я степень равна единице, являются вычетами, можно и не прибегая к рассуждению о количестве корней: достаточно заметить, что для таких чисел работает вышеизложенный алгоритм Тонелли.

Классические алгоритмы

Фальсификация простоты

Сначала напомним классический способ проверки числа \(N\) на простоту: для каждого \(x\geqslant 2\), для которого \(x^2 \leqslant N\), проверить, делится ли \(N\) на \(x\):

• если делится, то \(N\) составное
• если не делится, то \(N\) простое

Работоспособность этого алгоритма основана на том, что если \(N=ab\) для положительных \(a\) и \(b\), то из свойств порядка действительных чисел тривиально следует, что:

• либо \(a\leqslant\sqrt{N}\)
• либо \(b\leqslant\sqrt{N}\)
• либо верно и то, и другое

Поэтому, если у \(N\) есть какой-то положительный делитель, отличный от \(1\) и \(N\), то есть и делитель (тоже отличный от \(1\) и \(N\)), не превышающий \(\sqrt{N}\).

Основная проблема этого алгоритма: долгое время работы. Например, для того, чтобы подтвердить простоту 100-значного простого числа, потребуется проверить порядка \(10^{50}\) потенциальных делителей (такую проверку невозможно осуществить при помощи известных сейчас технологий построения вычислительных устройств даже за ожидаемое время существования Солнечной системы).

Поэтому сейчас мы поговорим о более быстрых способах проверки числа на простоту.

Тест Ферма

Согласно формуле Эйлера, если \(p\) — простое и \(x\) не кратен \(p\), то

\[ x^{p-1} \equiv_p 1 \]

Напомним, что это равенство также называют Малой Теоремой Ферма.

Будем говорить, что число \(x\) удовлетворяет тесту Ферма по модулю \(N\), если

\[ x^{N-1} \equiv_N 1 \]

Оказывается, что если хотя бы одно \(x\), взаимно простое с \(N\), не удовлетворяет тесту Ферма (и тем самым доказывает, что \(N\) составное), то среди всех чисел от \(1\) до \(N-1\) тех, кто не удовлетворяет тесту Ферма, не менее половины!

Действительно, пусть \(f_1, f_2, \ldots f_n\) — все остатки по модулю \(N\), которые удовлетворяют тесту Ферма. Пусть также \(x\) не удовлетворяет тесту Ферма и взаимно прост с \(N\). Тогда, очевидно:

• все \(xf_i\) различны (поскольку \(x\) взаимно прост с \(N\))
• все \(xf_i\) не удовлетворяют тесту Ферма (поскольку \((xf_i)^{N-1}\equiv_N x^{N-1}\cdot 1\))

Поэтому остатков, не удовлетворяющих тесту Ферма, не меньше, чем удовлетворяющих.

Вероятностная верификация простоты

Отрицательный тест Ферма (для ненулевого остатка) опровергает простоту числа. Положительный тест Ферма же не доказывает простоту. Но вот многократно повторённый тест Ферма в некоторых случаях позволяет быть уверенным в простоте числа.

А именно, очевидно следующее: если существует взаимно простой с \(N\) и не удовлетворяющий тесту Ферма остаток по модулю \(N\), то вероятность сделать \(n\) положительных тестов Ферма подряд (выбирая тестируемый остаток случайным образом) не превышает \(2^{-n}\). Например, для \(n=50\) эта вероятность существенно меньше вероятности того, что в вычислениях произошла ошибка из-за космического луча, попавшего в оперативную память.

К сожалению, никакого простого способа узнать, существует ли взаимно простой с \(N\) и не удовлетворяющий тесту Ферма остаток, нет.

Более того числа, для которых таких остатков не существует, называемые числами Кармайкла, встречаются не так уж и редко (известно, например, что в пределах от \(1\) до \(x\) асимптотически хотя бы \(x^{1/3}\) чисел являются числами Кармайкла).

Поэтому требуется более сильный тест на простоту.

Тест Миллера-Рабина

Ключевой частью алгоритма Тонелли является многократное возведение в квадрат чисел вида \(a^q\), где \(q\) — нечётное число вида \((p-1)/2^s\).

При этом

• либо \(a^q\equiv_p 1\)
• либо на каком-то шаге, номер которого меньше \(s\), получится \(-1\)

Будем говорить, что \(a\) удовлетворяет тесту Миллера-Рабина по модулю \(N=2^s q + 1\), где \(q\) нечётно, если

• либо \(a^q\equiv_N 1\)
• либо менее чем \(s\)-кратное возведение \(a^q\) в квадрат даёт \(-1\) по модулю \(N\)

Оказывается, что для составного \(N\) не более четверти всех остатков удовлетворяет тесту Миллера-Рабина. Это не слишком легко доказывается, поэтому для полноты картины мы докажем более слабое (но не менее полезное) утверждение о том, что остатков, удовлетворяющих тесту Миллера-Рабина не более половины.

Недотеорема Рабина

Свойство чисел Кармайкла

Сперва заметим, что степени простых чисел не являются числами Кармайкла: если \(N=p^a\), где \(a\geqslant 2\), то \(p+1\) не удовлетворяет тесту Ферма.

Действительно, если бы \(p+1\) удовлетворяло тесту Ферма по модулю \(p^a\), то его \((N-1)\)-я степень была бы сравнима с единицей по любому модулю, делящему \(p^a\). В том числе — по модулю \(p^2\). Но

\[ (p+1)^{N-1} \equiv_{p^2} (N-1)p + 1 = p^{a+1} - p + 1 \equiv_{p^2} 1-p \]

Поэтому любое число Кармайкла можно представить в виде произведения двух взаимно простых нечётных чисел, отличных от 1.

Рабиновские лжецы

Если \(N\) не число Кармайкла, то мы уже доказали, что не менее половины остатков не удовлетворяют тесту Ферма (а, следовательно, и тесту Миллера-Рабина).

Осталось рассмотреть ситуацию, когда \(N\) — число Кармайкла.

Пусть \(r_1, r_2\ldots r_n\) — все остатки, удовлетворяющие тесту Миллера-Рабина. Заметим, что среди них есть число \(N-1\), которое на нулевом шаге теста даёт минус единицу. Пусть \(M\) — максимальный номер шага, на котором кто-то из \(r_i\) даёт минус единицу (в непустом конечном множестве чисел максимум всегда есть).

Рассмотрим вообще все остатки, для которых \(K\)-кратное возведение в квадрат их \(q\)-й степени даёт единицу или минус единицу. Будем называть их «хорошими». Заметим, что:

• произведение хороших остатков хорошее
• если \(h\) хороший, то он взаимно прост с \(N\)
• если \(h\) хороший, то его обратный по модулю \(N\) остаток тоже хороший
• если \(h\) хороший, а \(x\) не хороший, то \(hx\) тоже не хороший

Поскольку все \(r_i\) хорошие, то их не меньше, чем хороших остатков. А в случае, когда есть не хороший остаток, хороших остатков не более половины.

Осталось заметить, что не хороший по модулю числа Кармайкла остаток всегда есть. Пусть \(N=AB\), где \(A\) и \(B\) взаимно просты, нечётны и не менее тройки.

Пусть \(r\) — тот самый остаток, удовлетворяющий тесту, для которого требуется ровно \(K\) возведений в квадрат для получения минус единицы.

Выберем любой остаток, сравнимый с \(r\) по модулю \(A\) и сравнимый с \(1\) по модулю \(B\): такой существует благодаря КТО. \(K\)-кратный квадрат его \(q\)-й степени сравним с \(-1\) по модулю \(A\) и сравним с \(1\) по модулю \(B\).

Если бы наш остаток был хорошим, то по модулям \(A\) и \(B\) должны были получиться либо две минус единицы, либо две единицы. Но единица не сравнима с минус единицей по модулю, большему двойки!

Решето Эратосфена

Генерация простых чисел

Быстрое возведение в степень

Длинная арифметика

Для всех ранее изученных алгоритмов требуется эффективная арифметика больших чисел (не умещающихся в регистры процессора).

Наиболее банальный способ представления больших чисел — последовательность цифр в какой-нибудь системе счисления (обычно с основанием \(2^{k}\), где \(k\) — разрядность процессора ЭВМ).

При таком представлении сложение чисел «в столбик» имеет сложность, пропорциональную максимальному количеству цифр складываемых чисел.

С умножением всё хуже — для умножения двух \(N\)-значных чисел «в столбик» вычислительная сложность составляет \(N^2\).

Сейчас мы рассмотрим простейший (и заодно — исторически первый) способ умножать числа быстрее, чем просто «в столбик».

Алгоритм Карацубы

Пусть \(d\) — основание используемой нами системы счисления и мы умножаем два \(2N\)-значных числа:

\[ (A d^N + B)\cdot (X d^N + Y) = AX d^{2N} + (AY + BX) d^N + BY \]

В 1960-м году А.А. Карацуба на одном из семинаров А.Н. Колмогорова заметил, что в вышенаписанном равенстве можно выбрать \(d=1\), что даст полезное соотношение

\[ AY+BX = (A+B)(X+Y) - AX - BY \]

То есть для нахождения всех цифр произведения можно использовать не четыре \(N\)-разрядных умножения и три \(2N\)-разрядных сложения, а три \(N\)-разрядных умножения, два \(2N\)-разрядных сложения и два \(N\)-разрядных сложения.

Пример

Вычислим алгоритмом Карацубы \(57\cdot 28\):

\[ \begin{aligned} 5\cdot2 & = 10 \\ 7\cdot8 & = 56 \\ 5\cdot8 + 7\cdot 2 & = (5+7)\cdot(2+8) - 10 - 56 = 12\cdot 10 - 66 = 120 - 66 = 54 \end{aligned} \]

Итого \(57\cdot 28 = 1000 + 540 + 56 = 1596\).

Протокол Диффи-Хеллмана

Шифрование RSA