А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 8

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

Текст из файла (страница 8)

Если m₁, m₂, … , m_k – попарно простые числа, то сравнение

f(x)≡0(mod m₁·m₂·…·m_k) *

равносильно системе

** ,

причем, если первое сравнение имеет T₁ решений по модулю m₁, второе – T₂ решений модулю m₂, …, k-е сравнение имеет T_k решений по модулю m_k, то исходное сравнение будет иметь T=T₁·T₂·…·T_k решений по модулю m₁·m₂·…·m_k.

Доказательство:

Равносильность сравнения и системы очевидна и следует из свойств 12 и 13 сравнений.

Утверждение о количестве решений следует из того, что каждое сравнение

f(x)≡0(mod m_s) ***

выполняется тогда и только тогда, когда выполняется одно из T_s сравнений вида x≡b_s(mod m_s) (где b_s пробегает вычеты решений сравнения ***). Причем возможно всего T=T₁·T₂·…·T_k различных комбинаций вида x≡b₁(mod m₁), x≡b₂(mod m₂),…, x≡b_k(mod m_k), которые приводят (по китайской теореме об остатках) к различным классам вычетов по модулю m₁·m₂·…·m_k.

□

Из доказанной теоремы следует, что решение сравнения вида сводится к решению сравнений вида .

А решение сравнение вида f(x)≡0(mod p^α) может быть найдено, если известно решение сравнения f(x)≡0(mod p). Покажем это.

Пусть x≡x₁(mod p) – решение сравнения f(x)≡0(mod p). Тогда x можно представить в виде

x=x₁+pt₁, где .

Подставляя такое x в сравнение f(x)≡0(mod p²) и применяя формулу Тейлора (учитывая, что f(x) – многочлен, x₁ – целое число, поэтому ), получаем

f(x₁)+pt₁f '(x₁)≡0(mod p²).

Поскольку f(x₁)≡0(mod p), то p\f(x₁), а значит можно сократить в получившемся выражении на p правую, левую части и модуль. Получим:

Если f '(x₁) не делится на р, то данное сравнение имеет одно решение:

(т.е. )

Подставляя полученное x в сравнение f(x)≡0(mod p³), имеем

f(x₂)+p²t₂f '(x₂)≡0(mod p³),

откуда, сократив правую, левую части и модуль на p² , получим

[Здесь f '(x₂) не может быть кратно р, если f '(x₁) не кратно p, т.к. x₂≡x₁(mod p), а значит, f '(x₂) ≡ f '(x₁) (mod p)]

Тогда сравнение имеет одно решение , или, что то же самое, , откуда получаем решение по модулю p³ : x=x₃+p³t₃.

Продолжим этот процесс до тех пор, пока не будет решено сравнение по модулю p^α. Итак, по данному решению сравнения f(x)≡0(mod p) можно найти решение сравнения f(x)≡0(mod p^α).

Пример:

Требуется решить сравнение x³+9x—1≡0 (mod 125).

Известно, что сравнение x³+9x—1≡0 (mod 5) имеет одно решение:

x≡2(mod 5), или x=2+5t₁.

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

Подставим получившееся x в сравнение по модулю 25:

(2+5t₁)³+9(2+5t₁)—1≡0 (mod 25).

Решим это сравнение.

8+4·5t₁+2·(5t₁)²+(5t₁)³+18+9·5t₁—1≡0 (mod 25)

25+13·5t₁+25·(5t₁³+2 t₁²) ≡0 (mod 25)

13·5t₁≡0 (mod 25)

13t₁≡0 (mod 5)

t₁≡0 (mod 5)

Или, что то же самое, t₁=0+5t₂, откуда решение по модулю 25 есть x=2+25t₂. Подставим полученное x в сравнение по модулю 125:

(2+25t₂)³+9(2+25t₂)—1≡0 (mod 125)

Решим это сравнение.

8+4·25t₂+2·(25t₂)²+(25t₁)³+18+9·25t₁—1≡0 (mod 125)

25+13·25t₂+625·(25t₂³+2t₂²) ≡0 (mod 125)

25+13·25t₂≡0 (mod 125)

1+13t₂≡0 (mod 5)

13t₂≡—1 (mod 5)

3t₂≡4 (mod 5)

Получили сравнение первой степени. Решим его. Отыщем 3^-1(mod 5), для чего, как всегда, воспользуемся расширенным алгоритмом Евклида:

5=3+2

3=2+1

2=1+0

1=3—2=3—(5—3)=2·3—1·5.

2≡3^-1(mod 5).

Тогда решением сравнения относительно t₂ будет

t₂≡2·4 (mod 5)

t₂≡3 (mod 5)

Или, что то же самое, t₂=3+5t₃, откуда решение по модулю 125 есть x=2+25(3+5t₃)=2+75+125t₃=77+125t₃, или, что то же самое,

x≡77 (mod 125).

§5. Теория квадратичных вычетов

Рассмотрим сравнение xⁿ≡a(mod m) *, (a,m)=1. Если * имеет решение, то а называется вычетом степени n по модулю m. Если n=2, то вычеты называются квадратичными, если n=3 – кубическими, n=4 – биквадратичными. Если * решений не имеет, то а называется невычетом степени n по модулю m.

Далее будем рассматривать случай n=2, т.е. сравнения вида x²≡a(mod m), (a,m)=1.

5.1. Квадратичные вычеты по простому модулю.

В этом пункте будем рассматривать сравнения вида x²≡a(mod p), p>2 – простое число.

Теорема 1.

Если а – квадратичный вычет по простому модулю р, то сравнение x²≡a(modp) имеет ровно 2 решения.

Доказательство:

Если а – квадратичный вычет по модулю p, то найдется хотя бы одно решение исходного сравнения: x≡x₁(mod p).

Но, поскольку (—x₁)²=x₁², то решением также является x≡—x₁(mod p), причем x₁ —x₁(mod p), т.к. р – нечетное число.

Более двух решений данное сравнение иметь не может, так как является сравнением второй степени (§4, п.3, Теорема 2).

□

Теорема (о числе квадратичных вычетов)

Приведенная система вычетов по модулю p состоит из квадратичных вычетов и квадратичных невычетов.

Доказательство:

Среди вычетов приведенной системы по модулю p квадратичными вычетами являются только те, что сравнимы с квадратами чисел

…, –2, –1, 1, 2,…, , т.е. с числами 1, 2², 3²,…,

При этом квадраты не сравнимы между собой по модулю p, т.к. иначе из того, что k² ≡ l² (mod p), 0 < k < l следовало бы, что сравнению x²≡l²(mod p) удовлетворяют 4 числа: –l, l, –k, k, что противоречит Теореме 1.

Таким образом, квадратичных вычетов в приведенной системе по модулю p ровно штук. Остальные элементы приведенной системы являются квадратичными невычетами. А поскольку всего в приведенной системе по модулю p содержится p—1 элементов, то квадратичными невычетами являются также элементов.

□

Множество квадратных вычетов по модулю p обозначается Q(p), множество квадратичных невычетов – .

5.2. Символ Лежандра. Символ Якоби.

Символом Лежандра называется символ (читается «символ Лежандра а по р »). а называется числителем, р – знаменателем символа Лежандра. Символ Лежандра отвечает на вопрос, является ли число а квадратичным вычетом по модулю р.

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

Свойства символа Лежандра:

1. Критерий Эйлера:

2. a≡a₁(mod p)

8. 3акон взаимности: если p, q – нечетные простые числа

Докажем некоторые из этих свойств.

Теорема (Критерий Эйлера)

Если (p, a)=1

Доказательство:

По теореме Ферма, a^p--1≡1(mod p). В этом сравнении перенесем единицу в левую часть: a^p—1—1≡0(mod p). Поскольку p – простое, а значит нечетное число, значит p—1 – число четное. Тогда можем разложить левую часть сравнения на множители: .

Из множителей в левой части один и только один делится на p, то есть либо

*, либо **

Если а – квадратичный вычет по модулю р, то а при некотором x удовлетворяет сравнению a≡x²(mod p) , тогда , а учитывая (по теореме Ферма), что x^p—1≡1(mod p), получаем сравнение (*).

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

□

Свойство 2:

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

□

Свойство 3:

Для любого p выполняется 1≡1²(mod p), а значит «1» является квадратичным вычетом для любого модуля p.

□

Свойство 4:

Доказательство следует из критерия Эйлера при a=—1.

□

Свойство 5:

По критерию Эйлера, .

□

Доказательства прочих свойств можно произвести самостоятельно или найти в [5].

Итак, символ Лежандра можно найти, пользуясь либо критерием Эйлера, либо используя свойства 2-8:

Пример:

a)

10 – квадратичный вычет по модулю 13.

б)

.

1350 не является квадратичным вычетом по модулю 1381.

Пусть n – составное число, каноническое разложение которого есть . Положим (a,n)=1. Тогда символ Якоби определяется равенством:

Свойства символа Якоби:

1. a≡a₁(mod n)

2.

3.

4.

5.

6. 3акон взаимности:

(n,m)=1, n, m>0, n, m — нечетные числа .

Эти свойства нетрудно доказать, воспользовавшись определением символа Якоби и свойствами символа Лежандра.

Очевидно, для символа Якоби выполняются те же свойства, что и для символа Лежандра, за исключением только критерия Эйлера. Критерий Эйлера для символа Якоби не выполняется.

Приведенные свойства символа Якоби позволяют составить алгоритм для вычисления символа Якоби и символа Лежандра:

1. Выделяем из числителя все степени двойки:

1. Пользуясь св-вом 4, понижаем степень k:

1. Если k mod 2=1, то вычисляем пользуясь св-вом 5.

2. Символ преобразуем, пользуясь законом взаимности, и затем приводим числитель m по модулю знаменателя n₁ и повторяя для получившегося символа Якоби шаги 1-4, пока в числителе не останется 1 или —1.

В более формализованном виде алгоритм выглядит следующим образом:

Алгоритм вычисления символа Якоби:

Характеристики

Список файлов книги