Алгоритм Евклида для вычисления наибольшего общего делителя

 

 

Вычисление обратных величин

В арифметике действительных чисел нетрудно вычислить мультипликативную обратную величину а~1 для ненулевого а:

a^-1 = 1/a или a * a^-1 =1

Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку

 

 

В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения

4 * x º 1(mod 7)

эквивалентно нахождению таких значений х и k, что

4 * x º 7 * k +1

где х и k-целые числа.

Общая формулировка этой задачи -нахождение такого целого числа х, что

a * x(mod n) = 1

Можно также записать

a^-1 º x(mod n)

Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку

5 * 3 = 15 º 1(mod 14).

С другой стороны, число 2 не имеет обратной величины по модулю 14.

Вообще сравнение

a^-1 º x(mod n)

имеет единственное решение, если а и n - взаимно простые числа.

Если числа а и n не являются взаимно простыми, тогда сравнение

не имеет решения [45].

a^-1 º x(mod n)]

Сформулируем основные способы нахождения обратных величин. Пусть целое число а Î{0,1,2,..., n-1}. Если НОД(а, n)=1, то a * i (mod n) при 1 = 0,1,2,...,n-1 является перестановкой множества {0,1,2,...,n-1}.

Например, если а=3 и n=7(НОД(3,7}=1), то

3 * i (mod 7) при i = 0,1,2,…,6

является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества (0,1,2,...,6).

Это становится неверным, когда НОД(а, n)¹1. Например, если а=2 и n= 6, то

Если НОД(а, n) = 1, тогда существует обратное число а^-1, 0<а^-1<n, такое, что

a * a^-1 º 1(mod n)

Действительно, a * i(mod n) является перестановкой 0,1,..., n-1, поэтому существует i, такое, что

a * i º 1(mod n).

Как уже отмечалось, набор целых чисел от 0 до n-1 называют полным набором вычетов по модулю п. Это означает, что для любого целого числа а(а>0) его вычет r = a(mod n)-это некоторое целое число в интервале от 0 до n-1.

Выделим из полного набора вычетов подмножество вычетов, взаимно простых с п. Такое подмножество называют приведенным набором вычетов.

Пример. Пусть модуль n=11- простое число. Полный набор вычетов по модулю 11.

(0,1,2,…,10)

 

При формировании приведенного набора вычетов из них удаляется только один элемент-0. Приведенный набор вычетов по модулю 11 имеет 11-1=10 элементов.

Вообще приведенный набор вычетов по модулю простого числа n имеет n-1 элементов.

Пример. Пусть модуль n=10. Полный набор вычетов по модулю n =10

{0,1,2,3,4,5,6,7,8,9}.

Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этогоприведенного набора были исключены элементы:

0 (1 элемент),

кратные 2 (4 элемента),

кратные 5 (1 элемент),

т.е. всего шесть элементов. Вычитая их из 10, получаем 10-1-4-1=4. т.е. четыре элемента в приведенном наборе.

10. Асимметричные шифры. Свойства, принципы построения.

Криптографическая система с открытым ключом (также асимметричное шифрование, асимметричные шифры) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций f(x), что по известному x довольно просто найти значение f(x), тогда как определение x из f(x) сложно в смысле теории.

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x), можно вычислить x. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции f (ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Вход в систему теперь выглядит так:

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.