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

Лекция 13. Алгоритм вычисления квадратного корня в простом поле.

13.1. Зависимость алгоритма от свойств модуля.

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

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

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

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

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

Случай . Поскольку , то .

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

Если верно , то, очевидно, .

Иначе, .

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

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

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

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

Уточним представление числа : , где - нечетно и, очевидно, .

Основная идея алгоритма – построить соотношение вида .

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

Исходя из сравнения , мы будем строить соотношения, в которых показатель при будет снижаться вдвое, пока не станет равным .

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

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

Перейдем к алгоритму.

Очевидно, . Более того, т.к. квадратичный вычет, то и мы можем снизить показатель в два раза: .

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

Если в правой части получается 1, то двигаемся дальше. Заметим, что в правой части может получиться не ранее чем на втором шаге, т.е. при показателе и ниже. Предположим, что в правой части при указанном показателе получилась : .

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

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

Из левой части сравнения легко выражается квадратный корень, т.е. .

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

В итоге, получим сравнение вида , откуда, умножив обе части на , получим: .

13.2. Методика применения алгоритма.

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

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

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

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

По теореме Эйлера, имеем . Можно извлечь квадратный корень, разделив показатель на два. При этом значение корня равно 1, т.к. - квадратичный вычет и, следовательно, . Показатель можно разделить на два снова, но необходимо выяснить какому числу (1 или –1) равно значение квадратного корня. Итак, . Поскольку , то .

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

Нам остался один шаг, чтобы снизить показатель при восьмерке до . Делим показатели на два и вычисляем значение левой части: , , т.е. .

Нам вновь необходимо умножить обе части сравнения на , что дает .

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

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

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

.