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

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

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

Возьмем модуль m=5. И пусть a=8. Разделим a на m с остатком:

8=5·1+3.

Остаток r=3. Значит 8 [3]₅, и наименьший неотрицательный вычет числа 8 по модулю 5 есть 3.

Абсолютно наименьший вычет можно отыскать, вычислив r—m=3—5=—2, и сравнив абсолютные величины |—2| и |3|. |—2|<|3|, значит —2 – абсолютно наименьший вычет числа 8 по модулю 5.

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

{0; 1;…; m—1} = Z_m – полная система наименьших неотрицательных вычетов.

{– ;…; 0;…; } (если m–нечетное число) ;

{ — ,…,—1, 0, 1,…, } или {— ,…, —1, 0, 1,…, } (если m четное число) – полная система абсолютно наименьших вычетов.

Пример

Если m=11, то полная система наименьших неотрицательных вычетов есть {0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, а полная система абсолютно наименьших вычетов – {–5; –4; –3; –2; –1; 0; 1; 2; 3; 4; 5}.

Утверждение 1

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

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

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



Утверждение 2

Если (a, m) = 1, и x пробегает полную систему вычетов по модулю m, то ax+b, где b – любое число из Z, тоже пробегает полную систему вычетов по модулю m.

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

Чисел ax+b будет ровно m штук. Остается доказать, что любые 2 числа ax₁+b и ax₂+b несравнимы по модулю m, если x₁ x₂(mod m)

Доказательство от противного. Предположим, что ax₁+b ≡ ax₂+b (mod m) в силу 4-го св-ва сравнений, ax₁ ≡ ax₂ (mod m) в силу св-ва сравнений №9 и того, что (a, m) = 1, имеем x₁ ≡ x₂(mod m). Получили противоречие с тем, что x₁ x₂(mod m). Следовательно, предположение неверно, а значит верно обратное. То есть ax₁+b и ax₂+b несравнимы по модулю m, если x₁ x₂(mod m), что и требовалось доказать.



3.3. Приведенная система вычетов

Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же НОД. Особенно важны классы, для которых он равен 1.

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

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

Количество чисел в приведенной системе вычетов по модулю m, очевидно, равно φ(m).

Пример:

Приведенная система вычетов по модулю 15 есть {1; 2; 4; 7; 8; 11; 13; 14}. Заметим, что φ(15)=(5–1)∙(3–1)= 8 и действительно, в приведенной системе вычетов по модулю 15 ровно 8 элементов.

Утверждение 1

Любые φ(m) чисел, попарно несравнимых по модулю m и взаимно простых с m, образуют приведенную систему вычетов.

(Доказательство очевидно как в утверждении 1 пункт 2)

Утверждение 2

Если (a, m) = 1, x пробегает приведенную систему вычетов по модулю m, то ax тоже пробегает приведенную систему вычетов по модулю m . (Доказательство очевидно как в утверждении 2 пункт 2).

3.4. Обратный элемент.

Говорят, что элемент b называется обратным к a по модулю m, если a∙b≡1(mod m), и пишут b ≡ a^–1 (mod m).

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

Возникает вопрос – для всех ли элементов по данному модулю m существует обратный (по умножению), и если для каких-то элементов обратный существует, как его найти?

Для ответа на этот вопрос воспользуемся расширенным алгоритмом Евклида. Рассмотрим сначала взаимно простые число a и модуль m. Тогда, очевидно, (a,m)=1. Расширенный алгоритм Евклида позволяет получить числа x и y, такие, что ax+my=(a,m), или, что то же самое, ax+my=1. Из последнего выражения получаем сравнение ax+my≡1(mod m). Поскольку my≡0(mod m), то ax≡1(mod m), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю m.

Пример.

a=5, m=7. Требуется найти a^-1mod m.

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

7=5∙1+2

5=2∙2+1

2=1∙2

Обратный ход:

1=5–2∙2=5–(7–5∙1)∙2=5∙3–7∙2.

x=3, y=–2.

5^-1≡3(mod 7)

Проверка: 5∙3=15. 15≡1(mod 7).

Действительно, 3 является обратным элементом к 5 по модулю 7.

Итак, конструктивным образом убедились в том, что для чисел, взаимно простых с модулем, существует обратный по этому модулю. А существуют ли обратные элементы для чисел, не являющихся с модулем взаимно простыми?

Пусть (a,m)=d≠1. Тогда a и m представимы в виде a=d∙a₁, m=d∙m₁. Допустим, что для a существует обратный элемент по модулю m, то есть b: a∙b≡1(modm). Тогда a∙b= m∙k +1. Или, что то же самое, d∙a₁∙b= d∙m₁∙k +1. Но тогда по теореме 2 из §1 п.1, в силу того, что и левая часть данного уравнения, и первое слагаемое в правой части делятся на d, то d\1, а это не так, поскольку d≠1. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.

Итак, мы только что доказали

Теорему обратимости

a^-1 (mod m) (a, m) = 1.

■

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

3.5. Алгебраические структуры на целых числах.

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

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

Группой называют множество G с заданной на нем бинарной операцией •, если:

а) Операция • ассоциативна, то есть a,b,c G выполняется (a•b)•c=a•(b•c);

б) a•e=e•a=a (Если групповая операция называется сложением, то e называют нулевым элементом, если операция – умножение, то e называют единичным элементом.);

в) (Если групповая операция называется сложением, то x´ называют противоположным к x элементом, если операция – умножение, то обратным элементом.);

Если операция группы <G,•> коммутативна (то есть ), то группа называется коммутативной, или абелевой.

Утверждение 1

< Z_m , +(mod m)> — абелева группа.

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

Докажем, что Z_m вместе с операцией сложения по модулю m образуют абелеву группу. Действительно, операция сложения не выводит за пределы множества целых чисел, а Z_m покрывает своими вычетами всё Z, поэтому можно сказать, что операция +(mod m) задана на Z_m. Ассоциативность операции +(mod m) следует из ассоциативности сложения, в качестве нулевого элемента выступает «0», а в качестве противоположного к a выступает m—a. Коммутативность групповой операции следует из коммутативности сложения.



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

Утверждение 2

<U_m, · (mod m)> — абелева группа.

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

Докажем, что умножение по модулю m задано на приведенной системе вычетов по модулю m. Действительно, U_m покрывает своими вычетами всё Z кроме тех чисел, которые имеют с m общие нетривиальные делители. Результат умножения двух чисел, каждое из которых взаимно просто с m, также будет взаимно просто с m. Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же наибольший общий делитель. Это значит, что операция умножения по модулю m не выводит за пределы U_m, а значит задана на U_m.

Ассоциативность и коммутативность операции · (mod m) следует из ассоциативности и коммутативности умножения, единичным элементом является «1». Каждый элемент множества U_m имеет обратный согласно теореме обратимости в силу того, что все элементы U_m взаимно просты с m.



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

Кольцом называют непустое множество K вместе с заданными на нем бинарными операциями + и ∙ , если:

а) <K,+> — абелева группа;

б) Операция ∙ ассоциативна;

в) Операция ∙ дистрибутивна относительно + (то есть a∙(b+c)=(a∙b)+(a∙c), (a+b)∙c=(a∙c)+(b∙c));

Кольцо <K,+,∙> называют коммутативным, если операция ∙ коммутативна.

Кольцо <K,+,∙> называют кольцом с единицей, если x∙e=e∙x=x.

Полем называют коммутативное кольцо с единицей <P,+, ∙ >, в котором каждый ненулевой элемент обратим по операции ∙ .

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

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