1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти


Название1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти
страница2/8
Дата публикации05.05.2013
Размер0.98 Mb.
ТипДокументы
userdocs.ru > Информатика > Документы
1   2   3   4   5   6   7   8

11.Понятие сравнения. Основные свойства сравнений. Решение сравнений.

Будем рассматривать целые числа в связи с остатком от их деления на натуральное m, называемое модулем. Если 2 целых числа a и b имеют одинаковые остатки от деления на m, то они называются сравнительными по модулю m. Сравнимость чисел: a≡b(mod m).

Свойства сравнений:

  1. a≡b(mod m) ↔ m/(a-b);

  2. a≡b(mod m), b≡c(mod m)  a≡c(mod m);

  3. Сравнения можно складывать почленно: a1≡b1(mod m), a2≡b2(mod m), m/(a1-b1), m/(a2-b2) . В силу свойства 1: m/(a1-b1+a2-b2), m/((a1+a2)-(b2+b1)).

  4. Сравнения можно почленно перемножать: a1≡mq1+r1, b1≡mq1+r1, a2≡mq3+r2, b2≡mq4+r2. Тогда можно записать: a1a2=m(mq2+q1r1+q2r1)+r1r2; a1a2=r1r2(mod m); b1b2=r1r2(mod m).

  5. К обеим частям сравнения можно прибавить одно и то же число.

  6. Обе части сравнения можно умножить на одно и то же число

  7. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем. Пусть следующее имеет место: a1d≡b1d(mod m)  m/d(a1-b1) => m/(a1-b1), (m,d)=1.

  8. Обе части уравнения и модуль можно сокращать на общий делитель.

  9. a≡b(mod m1), a≡b(mod m2) => a≡b(mod (m1m2)).

Сравнения I степени: Рассмотрим сравнение ax=b(mod m) при условии (a,m)=1 (1). Под решением любого сравнения понимается класс вычетов по модулю m, один элемент которого (а значит и все) удовлетворяет сравнению. В рассматриваемом случае найдутся целые u и v такие, что au+bv=1, следовательно, имеет место следующее выражение: au=1(mod m). Будем называть u обратным а по модулю m. Умножим обе части сравнения (1) на u, тогда x=bu(mod m). Следовательно , сравнение имеет единственное решение по модулю m.

Положим (a,m)=d>1. Согласно свойству 10, условие d/b является необходимым условием разрешимости сравнения (1). Будем считать его выполненным.

Пусть a=a1d, b=b1d, m=m1d. Тогда рассматриваемое сравнение равносильно a1x=b1(mod m1). Имеем одно решение: x=x1(mod m1). По модулю m имеет d решение.

Теорема: Пусть НОД a и m равно d ((a,b)=d), то ax=b(mod m) разрешимо тогда и только тогда, когда d/b. В этом случае оно имеет d решений. При небольшом m сравнение ax=b(mod m) решается подбором. Чтобы его решить, достаточно найти такое число u, что au=1(mod m). Это выполняется с помощью алгоритма Евклида. В качестве u можно взять также u=a.
^ 13. Система вычетов. Полная система вычетов. Приведенная система вычетов. Функция Эйлера. Привести конкретные примеры.

Рассмотрим множество целых чисел а € Z, тогда натуральное число m € Z разбивает множество Z на m непересекающихся подмножеств следующим образом. Множество чисел, сравнимых по модулю числа m, Аi = {a € Z|a ≡ i (mod m)}, i=0,…,m-1, будем называть классами эквивалентности по модулю m. Любое число из класса эквивалентности по модулю m будем называть вычетом по модулю m. Совокупность вычетов, взятых по одному из каждого класса эквивалентности, называется полной системой вычетов по модулю m ( в полной системе вычетов, таким образом, всего m чисел). Непосредственно сами остатки при делении на m называется наименьшими неотрицательными вычетами и образуют полную систему вычетов по модулю m. Вычет ρ называется абсолютным наименьшим, если |ρ| наименьший среди модулей вычетов данного класса эквивалентности. (Пример: Пусть m=5. Тогда 0,1,2,3,4 – наименьшие неотрицательные вычеты, -2,-1,0,1,2 – абсолютно наименьшие вычеты. Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5). Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m. Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Приведенная система вычетов по модулю m содержит ф(m) штук вычетов, где ф(m) – функция Эйлера, по определению равная количеству чисел, меньших m и взаимно простых с m. (Пример: пусть m = 42. Тогда приведенная система вычетов есть: {1,5,11,13,17,19,23,25,29,31,37,41}). Функция Эйлера ф(а) есть количество чисел из ряда 0,1,2,…,а-1, взаимно простых с a. Пусть дано натуральное число , представленное в виде его канонического разложения на простые сомножители n = \prod_{i=1}^k p_i^{\alpha_i}

Тогда функция \varphi(n) = \prod_{i=1}^k p_i^{\alpha_i - 1} \left( p_i - 1 \right)называется функцией Эйлера. При этом полагается, что \varphi(1) = 1.Функцию Эйлера можно также представить в виде так называемого произведения Эйлера: \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),где p — простое число и пробегает все значения, участвующие в разложении n на простые сомножители.
15.Таблица Кэли для заданий конечной группы.

Существует удобный способ задания конечной группы в виде таблицы. Она обычно называется таблицей Кели. Все строки таблицы и столбцы помечаются элементами группы, а на пересечении строки, помеченной элементом a, и столбца, помеченного b, ставится ab(либо a+b). Например, для Z5, таблица Кели имеет такой вид(над числами рисуем”_”):

1

0

1

2

3

4

0

0

1

2

3

4

1

1

2

3

4

0

2

2

3

4

0

1

3

3

4

0

1

2

4

4

0

1

2

3

^ 14. Понятие группы и подгруппы, основные свойства группы. Абелева группа. Группа классов вычетов по модулю m.

Группой называется непустое множество G с определенной не нем бинарной алгебраической операцией ·, которая обладает свойствами: 1) ассоциативность: a· (b·c)=(a·b) ·c для любых a,b,c € G; 2) существует нейтральный элемент (единица), то есть такой элемент e € G, что g·e=e·g=g для каждого g € G; 3) каждый элемент g € G имеет обратный, то есть такой элемент h-1 € G, что g·h-1=h-1·g=e. Абелевыми, или коммутативными, называются группы (G, · ) со свойством 4) a·b=b·a для произвольных a,b € G. Всякий линейный код является абелевой группой относительно операции сложения. Подгруппой в группе (G, ·) называется всякое непустое подмножество H элементов множества G, которое в свою очередь является группой относительно той же операции. Обозначим классы вычетов по модулю m следующим образом 0,1,2,3,4(над числами рисовать “_”) и определим их сложение по модулю m=5. 1+2=3, 2+3=0, 2+4=1, эта группа обозначается Z5 – (аддитивная), группа класса вычетов по m=5, т.е. выполняется обычное сложение и при необходимости берется остаток от деления на 5. Аналогичным образом строится группа классов вычетов по любому модулю m: Zm.
^ 16. Кольца (подкольца) и поля. Поле Галуа. Правила сложения и умножения в поле с двумя элементами.

Кольцом называют множество С с двумя бинарными операциями, обозначающими символом “+”,”-“, такими, что:

1)R- абелева группа относительно операций сложения.

2)Операция “·” умножения ассоциативна, т.е. для всех a,b,c € R – (a·b) ·c= a·b·c. 3)Выполняются законы дистрибутивности, т.е. для всех a,b,c € R - a(b+c) =ab+ac и (b+c)a=ba+ca.

Если для любых двух элементов кольца справедливо соотношение ab=ba, то кольцо называется коммутативным. Кольцо называется кольцом с единицей, если оно имеет коммутативную единицу, т.е. такой элемент e, что ae=ea=a, для любой a € R. Два элемента кольца a≠b, a≠0, b≠0 называется делителями нуля, если ab=0. Кольцо называется областью целостности, если оно является коммутативным кольцом без делителей 0 и с единицей. Коммутативное кольцо называется полем, если его ненулевые элементы образуют группу относительно операции умножения. Иными словами, поле F представляет собой множество, по крайней мере двух элементов, в котором определены 2 операции: сложение и умножение, и выполняется следующие аксиомы: 1)множество элементов образуют коммутативную группу по сложению; 2)множество ненулевых элементов образую коммутативную группу по умножению; 3)для любых трех элементов множества a,b и c выполняется следующее соотношение: a(b+c)=ab+ac, следовательно поле F является коммутативным кольцом с единичным элементом по умножении, в котором каждый ненулевой элемент обладает обратным элементом(дистрибутивный закон). Кольцо классов вычетов Zm будет областью целостности, а значит и полем, только при простом m. Поле, обозначаемое, как GF(p), состоящее из конечного числа элементов p, называется конечным полем, или полем Галуа. Для любого числа p, которое является степенью простого числа Q существует поле, насчитывающее p элементов. Поле Zp классов вычетов, где p – простое число, называется полем Галуа порядка p и обозначается GF(p). Поле не может содержать менее 2 элементов. Поскольку в нем должны быть по крайней мере единичный элемент относительно операции сложения(0) и единичный элемент операции умножения(1). Поле включающее только элементы 0 и 1обозначаются GF(2). Правила сложения и умножения в поле с двумя элементами имеет вид:



+

0

1

0

0

1

1

1

0



*

0

1

0

0

0

1

0

1

Двоичные кодовые операции, являющиеся упорядоченными последовательностями из n элементов поля GF(2), рассматриваются в теории кодирования как частный случай последовательностей из n элементов поля GF(p). Подмножеством S кольца R называется подкольцом этого кольца, если оно замкнуто относительно имеющихся операций сложения и умножения и само образует кольцо относительно этих операций. Подкольцо H кольца R называется идеаом этого кольца, если для всех a € H, r € H – ra € H. Идеал H кольца R называется простым, если ab € H → a € H, либо b € H. Идеал H кольца R называется максимальный, если он не содержится ни в какой другом идеале, кроме самого кольца R.
^ 17. Основные понятия криптологии: шифрование, защита информации, криптология, криптография, криптоанализ, криптосистема.

Шифрование – процесс преобразования информации с целью сокрытия ее содержимого.

^ Защита информации – всевозможные средства и функции, обеспечивающие конфиденциальность, целостность информации или связи, включая средства и функции, предохраняющие от неисправности. Защита инфы включает криптографию, криптоанализ, защиту от несанкционированного доступа.

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

Криптосистема – это система осуществляющая криптографическое преобразование инфы, реализованная программно, аппаратно или программно-аппаратно.

Криптоанализ – это раздел прикладной математики, изучающий модель, методы, алгоритмы, программные и аппаратные средства анализа криптосистемы или ее входных и выходных сигналов с целью извлечения конфиденциальных параметров. Очевидно, что задачи криптографии в матем. смысле обратны задачам криптоанализа. Оба матем. раздела: криптография и криптоанализ вместе образуют новую науку – криптологию.
^ 18. Основные этапы развития криптологии и их характеристика. Особенности современного этапа.

В развитии криптологии выделяют 3 основных этапа:

  1. С др.времени (ХХ в до н.э.) – 1949г. Характерна частными, узкоспециальными и линейными простыми алгоритмами криптографии и криптоанализа. Без использования компьютеров этот этап часто называют этапом докомпьютерной криптологии.

  2. 1949-1976г. Берет свое начало с момента публикации работы американского ученого в области прикладной математики К.Шеннона «Теория связи в секретных системах». Характеризуется проведением активных исследований в области криптологии с помощью ЭВМ. Криптология становится матем. наукой, однако в тот период она была закрытой наукой, т.к. основными потребителями были ___связи и информация в дипломатических военных организациях.

  3. 1976г – наше время. Начинается с момента публикации работы американских математиков У.Дидхри, М.Хеллман «Новое направление криптографии». В работе показано, что секретная передача информации возможна без передачи ключа. Этот этап называется открытой криптологией. Главная особенность этапа – массовое применение криптографии в банковском деле, компьютерных сетях(Internet) и др.приложениях.

На развитие криптографии в развитых странах выделяются значительные финансовые средства. Характерно также то, что криптология в значительной степени стимулирует развитие информатики. Современная криптология широко использует теорию вероятностей, мат.статистику, алгебру, теорию чисел, алгоритмов и сложности вычислений. Процесс шифрования осуществляется на мощных специализированных компьютерах, называемых устройствами шифрования.
^ 19. Криптографические системы, функционирующие по принципу подстановки. Характеристика систем, их особенности, основные отличия от других классов систем.

Криптографические системы, основанные на методе подстановки, разделяются на 4 основных класса:

  1. monoalphabetic;

  2. homophonic;

  3. polyalphabetic;

  4. polygram.

В системах класса monoalphabetic символ исходного текста заменятся другим символом таким образом, что между ними существует однозначное соответствие. То есть каждый символ исходного текста однозначно заменяется его подстановкой. Криптографическим ключом такой системы является таблица соответствия исходного алфавита алфавиту подстановки.Любой шифратор класса monoalphabetic может быть представлен в виде полиномиального преобразования порядка t:


Алгоритм Цезаря является полиномиальным алгоритмом нулевого порядка.

В криптографических системах класса homophonic имеется несколько вариантов замены исходного символа. Например, буква A может быть заменена цифрами 24, 35, 37, а буква B – цифрами 41, 17, 76. Тогда слово ABBA может быть зашифровано как (37, 17, 76, 24) или (35, 41, 76, 37) и т. д.

Подобные системы характеризуются значительно большей криптографической стойкостью, чем системы класса monoalphabetic.

Криптографические системы класса polyalphabetic основаны на использовании нескольких различных ключей. Большинство шифраторов подобного типа являются периодическими с периодом P. Исходный текст вида:



шифруется с помощью ключей :



Для p = 1 будем иметь шифр класса monoalphabetic.

Криптографические системы класса polygram характеризуются подстановкой не одного, а нескольких символов в исходном тексте. В общем случае n символов исходного текста заменятся n символами шифротекста.
1   2   3   4   5   6   7   8

Похожие:

1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconИнформация. Понятие информации. Формирование информации (схема)....
В информатике под информацией понимается сообщение, снижающее степень неопределенности знаний о состоянии предметов или явлений и...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconНачальник кафедры Уиит полковник полиции
Актуальность защиты информации. Понятие информации, информационной сферы, безопасности информации. Автоматизированные системы обработки...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconМатериал для подготовки
Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconЭкзаменационные вопросы по курсу
Понятие информации. Свойства, виды и формы информации. Единицы измерения информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconЛекция 3 Понятие информации, измерение информации
...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconВопросы к зачёту по дисциплине «Медицинская информатика» для студентов 1 курса
История информатики. Медицинская информатика. Понятие информации. Основные свойства информации. Виды информации. Виды медицинской...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconДля гос экзамена по курсу «Базы данных» 2011 год
Понятие экономической информации. Требования, предъявляемые к экономической информации. Виды экономической информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconТема Понятие информации
Основы защиты информации и сведений, составляющих государственную тайну; методы защиты информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти icon!!!Сообщения, данные, сигнал, атрибутивные свойства информации, показатели...
Информацию рассматривают с точки зрения ее практической полезности для получателя
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconПонятие «информация», откуда возникает, с чем связано, меры информации?
Эволюция информационных технологий в зависимости от развития процессов хранения, транспортирования и обработки информации
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница