Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел заключается в проведении следующей последовательности операций деления с остатком:
a = q-b+ г, где 0 <г <Ъ, b = qx-r + rb где 0<г|<г, г = q2'r і+ г2, где 0 < г2 < гх,
г\ =ЧЪ'Г2+ГЪ’ где <г2,
461
Приложение з
rk = Як+2 ¦ rk+1 + rk+2> где 0 < rk+2 < rk+1.
r\ - Яз * r2 + Г3 ’ ГДе O - r3 < r2 •
Корректное завершение алгоритма гарантируется тем, что остатки от делений образуют строго убывающую последовательность натуральных чисел. Из приведенных равенств следует, что
(а, b) = (Ъ, г) = (г, г, ) = ... = (гя_, ,гп) = гп.
Поэтому наибольший делитель чисел а и b совпадает с гп.
Как следствие из алгоритма Евклида, можно получить утверждение, что наибольший делитель целых чисел а и b может быть представлен в виде линейной комбинации этих чисел, т. е. существуют целые числа Unv такие, что справедливо равенство
а • и + b • V = гп.
Вычисление обратного элемента по заданному модулю
Если целые числа а и п взаимно просты, то существует число а\ удовлетворяющее сравнению a -a' = l(mod п). Число а' называют обратным к а по модулю п и используют обозначение а'] (mod п). Вычислить а' можно, например, воспользовавшись представлением наибольшего общего делителя чисел а и п в виде их линейной комбинации: а • и 4- b • п = 1. Взяв наименьшие неотрицательные вычеты обеих частей этого равенства по модулю п, получим, что искомое значение d удовлетворяет сравнению а' = и (mod п).
462
Цементы алгебры и теории чисел
Вычисление обратных величин по некоторому модулю может быть выполнено более просто, если использовать некоторые факты из теории чисел.
Функцией Эйлера называется функция (р{п\ определенная на множестве натуральных чисел и равная количеству целых чисел в промежутке [1, и], взаимно простых с п.
Если известно, что п- р1^1 pkt*, где р{P1 — различные простые числа, то формула вычисления функции Эйлера имеет вид
<р(«)=П(р7-1)-р*у_|-
J=і
Справедлива малая теорема Ферма: если п — простое число и HOД(а, п) = 1, то
ап~~х = I (mod п).
Обобщение малой теоремы Ферма, полученное Эйлером, утверждает: если НОД(а, п) = 1, то
ап~х s I (mod п).
С учетом приведенных фактов получаем, что наиболее просто значение а~х (mod п) находится из соотношения
а~х = (mod п).
Китайская теорема об остатках
Любое целое неотрицательное число, не превосходящее произведения натуральных чисел , можно одно-
значно восстановить, если известны его вычеты по этим модулям. Этот результат, полученной в I веке китайским мате-
463
І Іриложение З
матиком Сун Це, носит название китайской теоремы об остатках.
Математическая формулировка этого результата такова: Теорема. Пусть — попарно взаимно про-
стые числа. Тогда для любых целых чисел а1,а2,...,а1 сравнения
х = а{ (mod тх) , х = at (mod mt)
имеют в интервале [0,А/-1], M = тх -т2 mt единственное общее решение вида
х = ^jCij • Nj • Mj (mod М),
где M = — ,а W =M;1 modm j = 1,...,/.
ntj
Алгебраические структуры
Множество элементов G с заданной на нем бинарной операцией называется группой, если выполнены три усло-
вия:
1) операция ” ассоциативна, то есть (а • Ь) • с = а - (Ь • с) ,
2) существует элемент е из G, такой, что для любого g из G выполняются равенства е • g = g * е = g,
3) для любого g из G существует элемент g7 из G CO свойством g- g' = g' - g = e .
Обычно используется обозначение (G5 ).
Элемент е из G называют нейтральным элементом группы, а элемент g' — обратным элементом к g. Для обратного элемента обычно используется обозначение g'=g_1. Следует
464
Элементы алгебры и теории чисел
отметить, что в группе G нейтральный элемент и элемент, обратный к элементу g, определены однозначно.
С точки зрения решения уравнений основное свойство группы состоит в том, что в ней однозначно разрешимы уравнения вида
a • х = b, у-а- Ь
при любых a.beG.
Заметим, что если при всех я, b и с эти уравнения однозначно разрешимы относительно х и у, то (G, •) называется квазигруппой. Для квазигруппы не обязательно выполняются условия 1)—3) из определения группы. Вместе с тем ассоциативная квазигруппа всегда является группой.
Операция называется коммутативной, если для любых двух элементов а и b из G выполнено равенство а • b = b - а. В этом случае группа G называется коммутативной или абелевой.
Примером группы является множество комплексных корней степени п из 1 с операцией умножения корней как комплексных чисел.
Множество R с двумя бинарными ассоциативными операциями сложения “+” и умножения называется кольцом,
если выполнены следующие условия:
— множество R с бинарной операцией сложения является абелевой группой,
— операция удовлетворяет условию дистрибутивности относительно операции т. е. (а + Ь) • с - а • с 4- Ъ • с и a-(b + c) = a-b + a-c.
Если операция коммутативна, то кольцо называется коммутативным.
Примером кольца является множество Zw, образующее полную систему вычетов целых чисел по модулю п с операциями сложения и умножения по модулю я, причем это кольцо является коммутативным.
