Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 121

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 115 116 117 118 119 120 < 121 > 122 123 124 125 .. 126 >> Следующая


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

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, образующее полную систему вычетов целых чисел по модулю п с операциями сложения и умножения по модулю я, причем это кольцо является коммутативным.
Предыдущая << 1 .. 115 116 117 118 119 120 < 121 > 122 123 124 125 .. 126 >> Следующая

Реклама

Запчасти для гбо

Запчасти и комплектующие

rgo-rm.ru

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed