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

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

Целое число а делит без остатка другое целое число b, если и только если

b = k • a

для некоторого целого числа k. В этом случае аназывают делителем числа bили множителем в разложении числа bна множители.

Пусть а – целое число, причем а > 1. Тогда а является простым числом, если его единственным положительным делителем будут 1 и само а. В противном случае а называется составным.

Любое целое n > 1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение простых.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители. Не было получено и никакой нетривиальной нижней оценки временной сложности разложения. Никаких эффективных методов не известно даже в таком простом случае, когда необходимовосстановить два простых числа p и q из их произведения:

n = p • q.

Наибольший общий делитель чисел а и b, обозначаемый как
НОД (а, b) или просто (а, b), это наибольшее целое, делящее одновременно числа а и b.

В эквивалентной форме (а, b) – это то единственное натуральное число, которое делит а и b и делится на любое целое, делящее и а и b.

Если НОД (а, b) = 1, то целые а и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Евклид описал этот алгоритм в своей книге “Начала”, написанной около 300 лет до н.э. Он не изобрел его. Историки полагают, что этот алгоритм, возможно, старше еще на 200 лет. Это древнейший нетривиальный алгоритм, который просуществовал до настоящего времени и все еще хорош и сегодня.

Опишем алгоритм Евклида для нахождения НОД (а, b).

Введем обозначения: q _i – частное , r _i – остаток.

Тогда алгоритм можно представить в виде следующей цепочки равенств:

а = b • q ₁ + r ₁, 0 < r ₁ < b,

b = r ₁ • q ₂ + r ₂, 0 < r ₂ < r ₁,

r₁ = r ₂ • q ₃ + r ₃, 0 < r ₃ < r ₂,

. .

. .

. .

r _{k - 2} = r _k - ₁ • q _k + r _k, 0 < r _k < r _{k - 1},

r _{k - 1} = r _k • q _{k + 1}.

Остановка гарантируется, поскольку остатки r _i от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что r _k есть общий делитель чисел а и b и, более того, что любой общий делитель чисел а и b делит и r _k. Таким образом, r _k = НОД (а, b) или r _k = (а, b).

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

а ^–1 = 1 / а или а • а ^–1 = 1.

{ Пример: мультипликативная обратная величина от числа 4 равна

1 / 4, поскольку

4 • 1 / 4 = 1. }

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

4 • х ≡ 1 (mod 7)

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

4 • х ≡ 7 • k + 1,

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

а • х (mod n) = 1.

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

а ^–1 ≡ х (mod n).

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

5 • 3 = 15 ≡ 1 (mod 14).

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

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

а ^–1 ≡ х (mod n)

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

Если числа а и n – не являются взаимно простыми, тогда сравнение
а ^–1 ≡ х (mod n)

не имеет решения.

Сформулируем основные способы нахождения обратных величин. Пусть целое число а Î {0, 1, 2, … , n - 1}.

Если НОД (а, n) = 1, то а • i (mod n) при i = 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 , то 2 • i (mod 6) º 0, 2, 4, 0, 2, 4 при

i = 0, 1, 2, … , 5. }

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

а • а ^–1 º 1 (mod n).

Действительно, а • i (mod n) является перестановкой 0, 1, 2, … , n – 1, поэтому существует i такое, что

а • i º 1 (mod n).

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

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

{ Пример. Пусть модуль n = 11 – простое число. Полный набор вычетов по модулю 11: {0, 1, 2, … , 10}. При формировании приведенного набора вычетов из них удаляется только один элемент: 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10 элементов. }

Таким образом, в общем случае приведенный набор вычетов по модулю простого числа n имеет n – 1 элемент.

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

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

Для произведения простых чисел p • q = n приведенный набор вычетов имеет (p – 1) • (q – 1) элементов.

{ Пример. При n = p • q = 2 • 5 = 10 число элементов в приведенном наборе будет (p – 1) • (q – 1) = (2 – 1) • (5 – 1) = 4.

Пример. Приведенный набор вычетов по модулю 27 = 3 ³ имеет 18 элементов: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}. Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов). }

Отсюда: Для модуля в виде простой степени n ^r приведенный набор вычетов имеет n ^{r – 1} • (n – 1) элемент.

При n = 3, r = 3 получаем 3 ^{3 –1} • (3 – 1) = 3 ² • 2 = 18 элементов.

Число элементов в приведенном наборе вычетов характеризует функция Эйлера j(n).

Таблица 5.1 – Функция Эйлера j(n)

Модуль n	Функция j(n)
n n 2 . . . n r	n – 1 n • (n – 1) . . . n r – 1 • (n – 1)
p • q (p, q - простые) . . . . . . i ei (p i - простые)	(p – 1) • (q – 1) . . . . . . i ei (p i – 1)

Иначе говоря, функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.

Малая теорема Ферма: если n – простое и НОД (а, n) = 1, то

а ^{n – 1} º 1 (mod n).

Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (а, n) = 1, то

а ^j(n) º 1 (mod n).

Если n – простое число, то предыдущий результат, учитывая, что j(n) = n – 1, приводится к виду (малой теоремы Ферма)

а ^{n – 1} º 1 (mod n).