Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), – это наибольшее целое, делящее одновременно числа a и b. В эквивалентной форме (a,b) – это то, единственное натуральное число, которое делит a и b и делится на любое целое, делящее и a и b. Если НОД (a,b)=1, то целые a и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Опишем алгоритм Евклида для нахождения НОД(a,b). Введем обозначения: q_i – частное; r_i – остаток. Тогда алгоритм можно представить в виде следующей цепочки равенств:

a = b ∙q₁ + r₁, 0 < r₁< b,

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

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

M M

r_k–2 = r_k–1 ∙ q_k + r_k, 0 < r_k< r_k–1,

r_k–1 = r_k ∙ q_k+1.

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

Отметим, что при операции умножения действительных чисел нетрудно вычислить мультипликативную обратную величину a^–1 для ненулевого числа a: a^–1 =1/a или a ∙ a^–1 =1. Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку 4 =1.

Обращаем особое внимание, что при операции умножения по модулю n в кольце Z/n={0,1,2,..,(n –1)} вычисление обратной величины для , т.е. величины x, для которой a∙x mod n =1 является более сложной задачей. Например, решение сравнения 4∙x º1 (mod 7) эквивалентно нахождению таких значений x и k, что 4∙x º 7∙k +1, где x и k – целые числа. Общая формулировка этой задачи – нахождение такого целого числа x, что

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) имеет единственное решение, тогда и только тогда когда a и n – взаимно простые числа.

В этом случае говорят, что элемент a обратим и его обратный элемент a^–1 равен x. Часто элемент a^–1 часто обозначают через . Но надо всегда понимать, что это целый положительный вычет по модулю n. Множество всех обратимых элементов кольца Z/n называется мультипликативной группой кольца вычетов Z/n. Эту группу обозначают через G или (Z/n)*. Оказывается, что элементa из Z/n обратим, тогда и только тогда, когда он взаимно прост с n, (a,n)=1. Через обозначают, так называемую, функцию Эйлера, значение от натурального числа n равно числу положительных целых чисел меньших n и взаимно простых с n. В связи с чем, число |G| элементов в мультипликативной группе вычетов кольца Z/n равно , .

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

Для произведения простых чисел p, q

=n, |G|=

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

Любой элемент a из группы G порождает подгруппу H =<a>={a,a²,a³,…,a^m}

Относительно умножения по модулю n порядок группы =<a>={a,a²,a³,…,a^m} (число ее элементов), совпадает с порядком элемента a – наименьшим натуральным числом m, при котором a^m º1 (mod n). Для g из G и ее подгруппе H={h₁,h₂,.., h_m} положим gH={gh₁,gh₂,…gh_m}. Легко видеть, что |H|=|gH| и при g не принадлежащим H их пересечение пусто. Любая группа имеет разложение по левым (правым) смежным классам по своей подгруппе, G=e (G= ), e – нейтральный элемент (в нашем случае e=1). Классы – подмножества (попарно не пересекаются и в объединении дают G). Из сказанного следует, что k|H|=|G| (теорема Лагранжа), Положим H==<a>, <a>={a,a²,a³,…,a^m}. Тогда |H| в нашем случае совпадает с порядком элемента a, |H|= m, то m делит |G|=j(n). По этой причине а^j(n) =а^cm для некоторого с и а^j(n) =а^cm= º(1)^с(mod n) для любого элемента а из G. Таким образом, справедливы теоремы:

· малая теорема Ферма: если n– простое и НОД (a,n)=1, то a^n–1 º1 (mod n);

· теорема Эйлера: если НОД (a,n) =1, то a^j(n) º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).

Получаем x = 5^–1 (mod 7) = 3. Результаты проверки сведены в таблицу.

Нахождение 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 7

a^–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.

Нахождение обратной величины a^–1 (mod n) с помощью расширенного алгоритма Евклида. Пусть НОД(а,n)=1, a>0, n>0. Рассматривается задача поиска целочисленного решения (x,y) уравнения a∙x-n∙y=1. Для решения задачи используют сначала алгоритм Евклида:

a = n ∙q₀ + r₁

n = r₁ ∙ q₁ + r₂

r₁ = r₂ ∙ q₂ + r₃

r₂ = r₃ ∙ q₃ + r₄

…………………

r_k–2 = r_k–1 ∙ q_k-1 + r_k

r_k–1 = r_k ∙ q_k +0

Находят последовательность q₀, q₁, q₂,…,q_k. Затем рекуррентно строят P₀,Р₁,Р₂,…,Р_k и Q₀,Q₁,Q₂,…,Q_k. Полагают

P_-2=0, P_-1=1 и P_j=q_jP_j-1+ P_j-2 для j 0,

Q_-2=1, Q_-1=0 и Q_j=q_jQ_j-1+Q_j-2 для j 0.

Искомые значения x, y находятся по формулам

.

Обратный элемент а^-1= (modn) для числа а есть решение уравнения

Вычисления в конечных полях. Поле F есть множество, на котором определены операции сложения и умножения, удовлетворяющие требованиям: ассоциативности, коммутативности, дистрибутивности, существования аддитивного 0 и мультипликативной 1, аддитивных обратных и мультипликативных обратных для всех элементов за исключением 0. Примерами простейших конечных полей являются кольца вычетов по простому модулю Z/p.

Конечное поле F(q) с конечным числом q элементов играет важную роль в криптографии. В общем случае число элементов конечного поля имеет вид

q = pⁿ,

где p – некоторое простое число и n ³1. Конечные поля называют полями Галуа и обозначают GF(pⁿ) или GF(p) при n =1. Многие криптосистемы шифров с открытым ключом базируются на полях Галуа GF(p), где p – большое простое число.

Пример. Поле Галуа GF(5) имеет элементы 0, 1, 2, 3, 4 и описывается следующими таблицами сложения и умножения.

Если p – простое число, то число a Î{1,…, p –1} является взаимно простым с p, и поэтому обратный элемент a^–1 существует. Тем самым однозначно определяется операция деления.

Обозначим через GF*(p) множество всех ненулевых элементов поля GF(p). Некоторый элемент g из GF*(p) называют образующим или порождающим элементом GF*(p), если для всех a из GF*(p) найдется такое целое x, что g^x = a modp. Всего имеется j(p–1) образующих элементов g. Число x называют дискретным логарифмом элемента a по основанию g и модулю p. Вычисление дискретных логарифмов (когда заданы g, a и p) примерно такая же труднорешаемая задача, как и задача разложения целого числа на множители.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма вычисления дискретных логарифмов. Более точно. Криптографическая стойкость ряда шифров с открытым ключом держится именно на отсутствии эффективного алгоритма вычисления дискретных логарифмов.

Картина мира - это...

a) совокупность мировоззренческих знаний о мире

b) художественное описание мира

c) естественнонаучное описание мира

d) географический атлас мира

Миропонимание, мировосприятие, мироотношение в своей совокупности образуют…

a) концепцию

b) мировоззрение

c) картину мира

d) теорию