Материал: Методические указания и контрольные задания по дисциплине информационная безопасность для студентов направления 09. 03. 02

Вообще приведенный набор вычетов по модулю простого числа 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, т.е. четыре элемента в приведенном наборе.Для произведения простых чисел 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) характеризует число элементов в приведенном наборе вычетов (табл. П.1).Таблица П.1

Модуль n	Функция j(n)
n – простое n2 … nr	n –1 n (n –1) … nr–1 (n – 1)
p * q (p, q – простые) … (pi – простые)	(p – 1) (q – 1) …

Иначе говоря, функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.Малая теорема Ферма: если n– простое и НОД (a,n)=1, тоa^n–1 º1 (mod n).Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (a,n) =1, тоa^j(n) º1 (mod n).Если n – простое число, то предыдущий результат, учитывая, что j(n) = n –1, приводится к виду (малой теоремы Ферма)a^n–1 º1 (mod n).

Основные способы нахождения обратных величин

a^–1 º 1 (mod n).

1. Проверить поочередно значения 1, 2, ..., n – 1, пока не будет найден a^–1 º1 (mod n), такой, что a*a^–1 (mod n) º 1.2. Если известна функция Эйлера j(n), то можно вы-числить

a^–1 (mod n) º a^j(n)–1 (mod n),используя алгоритм быстрого возведения в степень.3. Если функция Эйлера j(n) не известна, можно использовать расширенный алгоритм Евклида.Проиллюстрируем эти способы на числовых примерах.1. Поочередная проверка значений 1, 2, ..., n – 1, пока не будет найден x = a^–1 (mod n), такой что a * x º 1 (mod n).Пусть n = 7, a = 5. Требуется найти x = a^–1 (mod n).a * x º 1 (mod n) или 5 * x º 1 (mod 7).n – 1 = 7 – 1 = 6.Получаем x = 5^–1 (mod 7) = 3.Результаты проверки сведены в табл. П.2.Таблица П.2

x	5 * x	5 * x (mod 7)
1 2 3 4 5 6	5 10 15 20 25 30	5 3 1 6 4 2

2. Нахождение a^–1 (mod n), если известна функция Эйлера j(n).Пусть n = 7, a = 5. Найти x = a^–1 (mod n) = 5^–1 (mod 7). Модуль n = 7 – простое число. Поэтому функция Эйлера j(n) = j(7) = = n –1 = 6. Обратная величина от 5 по mod 7a^–1 (mod n) = a^j(n)–1 (mod n) == 5^6–1 mod 7 = 5⁵ mod 7 = (5² mod 7)(5³ mod 7) mod 7 == (25 mod 7)(125 mod 7) mod 7 = (4 * 6) mod 7 = 24 mod 7 = 3. Итак, x = 5^–1 (mod 7) = 3.3. Нахождение обратной величины a^–1 (mod n) с помощью расширенного алгоритма Евклида.Алгоритм Евклида можно обобщить способом, который имеет большое практическое значение. При этом способе во время вычисления НОД (a,b) можно попутно вычислить такие целые числа u₁ и u₂, чтоa * u₁ + b * u₂ = НОД (a,b).Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения.Квадратичные вычетыРассмотрим некоторое простое p > 2 и число a < p. Если число a сравнимо с квадратом некоторого числа x по модулю p, т.е. выполняется сравнение x² º a (mod p), тогда a называют квадратичным вычетом по модулю p. В противном случае a называют квадратичным невычетом по модулю p.Если a – квадратичный вычет, сравнение x² º a (mod p) имеет два решения: +x и –x, т.е. a имеет два квадратных корня по модулю p.Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, ..., (p –1)/2.Не все значения a < p являются квадратичными вычетами. Например, при p = 7 квадратичные вычеты это 1, 2, 4:1² = 1 º (mod 7),2² = 4 º 4 (mod 7),3² = 9 º 2 (mod 7),4² =16 º 2 (mod 7),5² = 25 º 4 (mod 7),6² = 36 º1 (mod 7).Заметим, что каждый квадратичный вычет появляется в этом списке дважды. Не существует никаких значений x, которые удовлетворяли бы любому из следующих уравнений:

x² º 3 (mod 7),x² º 5 (mod 7),x² º 6 (mod 7).Числа 3, 5 и 6 – квадратичные невычеты по модулю 7. Можно доказать, что существует точно (p –1)/2 квадратичных вычетов по модулю p и (p –1)/2 квадратичных невычетов по модулю p.Если a – квадратичный вычет по модулю p, то a имеет точно два квадратных корня: один корень между 0 и (p –1)/2, другой корень между (p –1)/2 и (p –1).Один из этих квадратных корней также является квадратичным вычетом по модулю p; он называется главным квадратным корнем.Вычиcление квадратных корней при p=7 представлено в табл. П.4.Таблица П.4

x2 º a (mod 7)	Корни
	x1	x2
12 º 1(mod 7) 22 º 4(mod 7) 32 º 2(mod 7)	+1 +2 +3	–1 = –1 + 7 = 6 –2 = –2 + 7 = 5 –3 = –3 + 7 = 4

Если n – произведение двух простых p и q, т.е. n = p * q, то существуют точно(p –1)(q –1)/4квадратичных вычетов по модулю n, взаимно простых с n. Например, по модулю 35 (p = 5, q = 7, n = 5 * 7 = 35) существуют = 6квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.