Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. Аудиторский риск - это...
  2. Б) Обучение рассказыванию по картинам
  3. Бит - это...
  4. Бит - это...
  5. Внутренняя картина болезни
  6. Воинская картина мира
  7. ВОПРОС 5. Научная картина мира. Структура и уровни организации материального мира. Синергетические представления о мироздании
  8. Всякая картина мира
  9. ГЛАВА IV. ПАТОЛОГИЯ ВОЗРАСТНЫХ ИЗМЕНЕНИЙ ПСИХИКИ. ДУШЕВНЫЕ БОЛЕЗНИ В КАРТИНАХ И ОБРАЗАХ
  10. ГЛАВА VIII ПСИХОПАТИИ ДУШЕВНЫЕ БОЛЕЗНИ В КАРТИНАХ И ОБРАЗАХ

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

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

a = b ∙q1 + r1, 0 < r1< b,

b = r1 ∙ q2 + r2, 0 < r2< r1,

r1 = r2 ∙ q3 + r3, 0 < r3< r2,

M M

rk–2 = rk–1 ∙ qk + rk, 0 < rk< rk–1,

rk–1 = rk ∙ qk+1.

Остановка гарантируется, поскольку остатки ri от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что rk есть общий делитель чисел a и b и, более того, что любой общий делитель чисел a и b делит и rk. Таким образом, rk = НОД(a, b) или rk = (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,a2,a3,…,am}

Относительно умножения по модулю n порядок группы =<a>={a,a2,a3,…,am} (число ее элементов), совпадает с порядком элемента a – наименьшим натуральным числом m, при котором am º1 (mod n). Для g из G и ее подгруппе H={h1,h2,.., hm} положим gH={gh1,gh2,…ghm}. Легко видеть, что |H|=|gH| и при g не принадлежащим H их пересечение пусто. Любая группа имеет разложение по левым (правым) смежным классам по своей подгруппе, G=e (G= ), e – нейтральный элемент (в нашем случае e=1). Классы – подмножества (попарно не пересекаются и в объединении дают G). Из сказанного следует, что k|H|=|G| (теорема Лагранжа), Положим H==<a>, <a>={a,a2,a3,…,am}. Тогда |H| в нашем случае совпадает с порядком элемента a, |H|= m, то m делит |G|=j(n). По этой причине аj(n)cm для некоторого с и аj(n)cm= º(1)с(mod n) для любого элемента а из G. Таким образом, справедливы теоремы:

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

· теорема Эйлера: если НОД (a,n) =1, то aj(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) º aj(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. Результаты проверки сведены в таблицу.

x 5 * x 5 * x (mod 7)
3   1

Нахождение 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) = aj(n)–1 (mod n) =

= 56–1 mod 7 = 55 mod 7 = (52 mod 7)(53 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 ∙q0 + r1

n = r1 ∙ q1 + r2

r1 = r2 ∙ q2 + r3

r2 = r3 ∙ q3 + r4

…………………

rk–2 = rk–1 ∙ qk-1 + rk

rk–1 = rk ∙ qk +0

Находят последовательность q0, q1, q2,…,qk. Затем рекуррентно строят P012,…,Рk и Q0,Q1,Q2,…,Qk. Полагают

P-2=0, P-1=1 и Pj=qjPj-1+ Pj-2 для j 0,

Q-2=1, Q-1=0 и Qj=qjQj-1+Qj-2 для j 0.

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

.

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

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

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

q = pn,

где p – некоторое простое число и n ³1. Конечные поля называют полями Галуа и обозначают GF(pn) или 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, что gx = a modp. Всего имеется j(p–1) образующих элементов g. Число x называют дискретным логарифмом элемента a по основанию g и модулю p. Вычисление дискретных логарифмов (когда заданы g, a и p) примерно такая же труднорешаемая задача, как и задача разложения целого числа на множители.

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

 

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

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

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

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

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

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

a) концепцию

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

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

d) теорию

 




Дата добавления: 2014-12-20; просмотров: 25 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Криптографические протоколы.| Определение информационной системы. Выполняемые функции.

lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав