Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Пример 2. Вернемся к примеру 1: покажем, как можно вычислить символ Лежандра, не разлагая 1872 на множители полностью, но лишь выделяя в нем максимальную степень 2. По квадратичному закону взаимности для символа Якоби имеем:
_ - (JLA (LL) - _ (ILH) - _ (LL]
~ V741i; ~ ~ \741iy 1.7411,/ -\117/-\Д17/'
это равняется - (^) (^) = (^) = (Ш) = (|) = -1.
Квадратные корни в кольце вычетов по модулю р. Используя квадратичный закон взаимности, можно быстро определить, является ли данное целое число а квадратичным вычетом или невычетом по модулю р. Однако если а — вычет, то этот факт не помогает решить сравнение х2 = a (mod р), — он лишь означает, что решение существует. В заключение этого параграфа мы приведем алгоритм, позволяющий для данного квадратичного вычета а найти его квадратный корень, если известен какой-либо невычет п.
Предположим, что р — нечетное простое число и предположим, что нам известен квадратичный невычет п по модулю р. Пусть а — такое целое число, что (-) = 1. Мы хотим найти такое целое число
2
х, что X = a (mod р). Для этого выполняем следующие действия. Во-первых, записываем р — 1 в виде 2°s (s нечетно). Вычисляем п" по модулю р и обозначаем его через Ь. Далее вычисляем а^"+1^2 по модулю р и обозначаем его через г. Покажем, что г в определенном смысле близко к квадратному корню из а. Точнее, покажем, что отно-шение г к а есть корень 2 -и степени из единицы по модулю р. Для краткости мы вместо сравнений по модулю р будем писать равенства
56
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
и через а обозначать обратный элемент к а по модулю р. Тогда
, -1 2x2а-1 32а-1 (р-1)/2 (а\ л
(а г ) = а = сг "=-)=1.
KpJ
Теперь нужно умножением г на некоторый корень 2°-й степени из 1 получить такой х, чтобы выполнялось равенство х /а = 1. Убедимся, прежде всего, что Ь есть примитивный корень 2°-й степени из единицы, т. е. что каждый корень 2°-й степени из единицы можно представить как степень Ь. Сначала заметим, что Ь есть корень 2а-к степени из единицы: Ь2 = пз2 = пр 1 = 1. Если бы корень Ь не был примитивным, то существовала бы некоторая меньшая его степень (делитель 2°), возведение в которую дало бы 1. Но тогда Ь был бы четной степенью примитивного корня 2°-й степени из 1, т.е. квадратом в Fp, что невозможно, так как b = п3, п — невычет, a s нечетно, и потому (jj) = (^У = -1. Таким образом, b — примитивный корень 2°-й степени из единицы. Остается найти подходящую степень Ь\ где 0 ^ j < 2°, так, чтобы х = b3r оказалось искомым квадратным корнем из а. Для этого представим j в двоичной записи j = jo + 2j\ + • ¦ ¦ + 2а Jc-2 и покажем, что можно последовательно определять, какие значения (0 или 1) принимают Jo,j\, ¦ ¦ ¦ (Заметим,
что всегда можно предполагать, что j < 2° \ так как b2 = — 1, и, следовательно, изменение J на 2 дает значение J , для которого bJ г является другим квадратным корнем из а.) Вот индуктивная процедура для нахождения двоичных цифр в разложении j.
1. Возводим г2/а в степень 2а 2. Как мы доказали, квадрат этого элемента есть 1. Следовательно, мы получаем ±1. Если мы получили 1, то полагаем Jq = 0, если мы получили —1, то полагаем Jq = 1. Заметим, что J0 тем самым выбрано так, что (bj0r)2/а является корнем 2° 2-й степени из единицы.
2. Пусть такие Jo,Ji,---,jk-i, что (Ь "' г) /а является корнем 2а к 1-я степени из 1, уже найдены, и мы хотим опреде-
а — к — 2
лить jk. Возводим полученный корень в степень 2 и выбираем
в зависимости от того, получается при этом +1 или —1:
ЄСЛИ {-O-J =(-1'
то берем Jk= соответственно. Легко проверить, что при таком выборе Jk «исправленное» значение оказывается ближе к квадратному
/, ?'o + 2i'i-|-----1-2*7* \2 / па-к-2 „ ,
корню из а, т. е. (о г) /а — корень 2 -и степени из 1.
§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ
57
Наконец, когда мы дойдем до к = а —2 и найдем ja-2, мы получим,
что
(bjo+2jl + -+2a~2ja-7r)2/a = 1,
т.е. b'1T — искомый квадратный корень из а, что и требовалось.
Пример 3. Используем предложенный алгоритм, чтобы найти квадратный корень из а = 186 по модулю р = 401.
4
Решение. Число п = 3 — невычет. Имеем р — 1 = 2 -25, поэтому 6 = З25 = 268 иг = а13 = 103 (вместо сравнений по модулю р пишем равенства). Вычислив а = 235, получим, что число г /а = 98 должно быть корнем степени 8 из единицы. Мы подсчитываем далее, что 984 = -1. Следовательно, jo = 1. Затем находим, что (6г) /а = —1. Так как квадрат этого числа равен 1, то = 0 и, наконец, j2 = 1. Итак, j' = 5 и искомый квадратный корень есть b5r = 304.
Замечания. 1. Наиболее простым этот алгоритм оказывается в случае, когда р = 3 (mod 4), р — простое. Тогда а — 1, s = (р — 1)/2 и (s + 1)/2 = (р + 1)/4. Легко проверить, что
(р+1)/4
X = г = а — искомый квадратный корень.
2. Оценим время работы этого алгоритма. Предположим, что невычет п известен с самого начала. Действия по нахождению s, Ь и г = a^s+1^2 (проводимые в кольце вычетов по модулю р) требуют не более O(log р) двоичных операций (см. предложение 1.3.6). Далее, при нахождении j наиболее трудоемкая часть А;-го шага индукции — возведение в степень 2° к 2 — требует а — к — 2 возведений в квадрат по модулю р чисел, меньших р. Так как а — к — 2 < а для каждого шага справедлива оценка O(alog р). Так как всего шагов а — 1, окон-
