Лекции по криптологии / Y20_M02_L11

Лекция 11.Сравнения с одним неизвестным.

11.1. Китайская теорема об остатках.

Следующее утверждение называется китайской теоремой об остатках.

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

При этом, , где , .

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

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

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

11.2. Общий метод решения линейных сравнений с одним неизвестным.

Сравнения вида могут иметь несколько решений, иметь единственное решение или не иметь решений вовсе. Если , то решение единственно: .

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

Теорема. Решения сравнения существуют тогда и только тогда, когда делит .

В этом случае, кроме исходного сравнения, разрешимо сравнение вида с единственным решением . Очевидно, все решения исходного сравнения в диапазоне являются числами вида , . В частности, если простое, то сравнение имеет не более одного решения.

11.3. Свойства степенных сравнений.

Квадратичным сравнением называется сравнения вида, где - неизвестный вычет.

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

Задача поиска решений квадратичного сравнения имеет важное значение в криптографии.

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

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

Теорема. Число ненулевых квадратичных вычетов равно числу квадратичных невычетов.

Пусть - квадратичный вычет по модулю нечетного простого числа .

Очевидно, при имеется единственное решение: .

Все ненулевые вычеты по модулю находятся среди чисел , следовательно, их квадраты составляют список и сравнение имеет решение, если принадлежит этому списку.

Далее, если , то имеется два очевидных решения: . Кроме того, количество решений не может превышать степени многочлена в левой части, т.е. двух. Чтобы убедиться, что решений в точности два достаточно показать, что . Однако, если это не так, то , что верно только для .

Заметим теперь, что в нашем списке квадратичных вычетов все вычеты попарно несравнимы. Действительно, если, например, и , то сравнение имело бы четыре решения: , , что невозможно. Таким образом, количество ненулевых квадратичных вычетов равно . Следовательно, количество квадратичных невычетов также равно .

11.4. Степенные сравнения.

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

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

Очевидно, при больших значениях переменных, решению задачи препятствует необходимость явного представления числа в виде .

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

Известен следующий результат: пусть - простое, , , тогда сравнение имеет решений.

Следствие. При получаем, что число первообразных корней в поле равно .

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

Переход к индексам показывает, что . Необходимое и достаточное условие разрешимости последнего сравнения заключается в том, чтобы делился на , т.е. .

Умножая модуль и обе части последнего сравнения на , получим

, откуда следует, что условие эквивалентно условию .

Следствие 1. (критерий Эйлера). Разрешимость сравнения эквивалентна выполнению условия .

Следствие 2. Пусть - примитивный элемент поля . Тогда квадратичный вычет в том и только том случае, когда в представлении число - четно.

Действительно, если , то дискретное логарифмирование дает , где модуль четен, следовательно, делится на два.

11.4. Первообразный корень в кольце вычетов по модулю .

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

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

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

Важная теорема.

Можно показать, что для многочлена от одной переменной с коэффициентами из , количество корней, лежащих в , не превосходит степени многочлена.

Рассмотрим пример на решение степенных сравнений.

Пример. Решить сравнение .

Таблица дискретных логарифмов считается известной. (Конкретные значения рассчитаны при и ).

Логарифмируя обе части сравнения, получаем:

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

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

Подставляя , окончательно получаем: .