Арифметика вычетов - раздел Образование, Основы теории информации и криптографии Будем Рассматривать Целые Числа В Связи С Остатками От Деления На Натуральное...
Будем рассматривать целые числа в связи с остатками от деления на натуральное число , называемое модулем.
,
(4.1)
где для некоторого целого .
Иногда называют вычетомпо модулю, – конгруэнтнымпо модулю.
Формулу (4.1) также можно интерпретировать следующим образом: если два числа имеют одинаковые остатки от деления на , то они сравнимы по модулю(например, ).
В отличие от (4.1) операция означает остаток от деления (например, ). Эта операция называется приведением по модулю.
Далее приведены свойства функции сравнения:
1. Сравнения по одинаковому модулю можно почленно складывать:,.
2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный: .
3. К любой части сравнения можно прибавить любое число, кратное модулю: .
4. Сравнения по одинаковому модулю можно почленно перемножать: ,.
5. Обе части сравнения можно возвести в одну и ту же степень.
6. Как следствие из вышеперечисленных свойств, получаем: ,,…,,
7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.
8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.
9. Если сравнение имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
10. Если сравнение имеет место по модулю , то оно имеет место и по модулю , равному любому делителю числа .
11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.
12. К обеим частям сравнения можно прибавить одно и тоже число; обе части сравнения можно умножить на одно и тоже число, взаимно простое с с модулем.
Свойство операции приведения по модулю: , где.
Пример
a) Проверим 7-ое свойство функции сравнения: , общие делители 24 и 6 – 2,3. Взаимно простое с 9 – это 2: . Тогда делим на 2 обе части сравнения: , иначе было бы неверно: .
b) Проверим свойство операции приведения:
Пример
Найдем при помощи свойства операции приведения по модулю:
Такой прием называется цепочкой разложения, в основе которой лежит двоичное представление числа[4]. ●
Числа, сравнимые по модулю , образуют класс вычетов по модулю. Все числа из одного и того же класса имеют один и тот же остаток от деления на . Любое число из класса вычетов называется вычетом по модулю .
Всего имеется классов вычетов по модулю (если классы обозначать как ): .
Свойства классов вычетов:
1. .
2. Æ.
3. Любые чисел попарно не сравнимые по модулю образуют полную систему вычетов.
4. Если и «пробегает» полную систему вычетов по модулю , то , где – любое число, также пробегает полную систему вычетов по модулю .
Полная система вычетов – это совокупность вычетов, взятых по одному из каждого класса эквивалентности.
Приведенная система вычетов по модулю– это совокупность всех вычетов из полной системы, взаимно простых с модулем .
Пример
Рис. 14. Иллюстрация к образованию классов вычетов по модулю 8
На рис. 14 изображен процесс «наматывания» цепочки целых чисел на колечко с делениями, при этом на одно деление автоматически попадают сравнимые между собой числа.
Существуют 8 классов вычетов по модулю . В каждом классе находятся числа, дающие при делении на одинаковые остатки:
Члены класса
0,8,16,
…
1,9,17,
…
2,10,15,
…
3,11,19,
…
4,12,20,
…
5,13,21,
…
6,14,22,
…
7,15,23,
…
Название класса
Например, одна из полных систем вычетов по модулю 8: 1200, 33, 42, 3, 12, 629, 22, 807.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Арифметика вычетов
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Задачи, решаемые в рамках теории информации
Теория информации – наука, появившаяся в 1948 г. в результате публикации работы Клода Шеннона «Математическая теория связи».
Ниже представлена структурная схема типичной системы передачи и
И их вероятностные модели
Пусть рассматривается произвольный источник сообщений. Каждое сообщение – это последовательность символов (например, букв русского алфавита, точек и тире в телеграфии, 0 и 1 в компьют
Собственная информация
Очевидно, что задача количественного измерения информации возникла при решении конкретных практических задач. Например, можно стремиться уменьшить количество электрических сигналов, необходимых для
Взаимная информация
Рассмотрим два ансамбля сообщений: . – ансамбль сообщений на входе
Энтропия
Пусть ИДС описывается некоторым дискретным ансамблем: . Тогда энтропия ИДС (или энтропия случайног
Условная энтропия
Пусть имеются два статистически независимых конечных ансамбля символов . Пары символов
Избыточность
Считают, что имеется избыточность, если количество информации, содержащейся в сигнале (энтропия сигнала), меньше того количества, которое этот сигнал мог бы содержать по своей физической природе.
Сжатие без потерь информации
В системах неразрушающего сжатия декодер восстанавливает данные источника абсолютно без потерь (рис. 4).
Сжатие с потерями информации.
Далее приведена система разрушающего сжатия (рис.5):
Рис. 5. Схема сжатия с потерями
&nbs
Без потерь информации
В данном случае кодирующие устройство должно удовлетворять следующим условиям:
1. Обеспечивать безошибочную передачу информации, то есть взаимно однозначное соответствие между
Основные методы побуквенного кодирования
Простейшими кодами, с помощью которых можно выполнять сжатие информации, являются коды без памяти. Наилучшим из кодов, обладающих свойствами, перечисленными выше, является код Хаффмана.
Ко
Код Хаффмана
Алгоритм Хаффмана дает эффективный способ поиска оптимального вектора Крафта. Код, получаемый с использованием этого оптимального вектора, называется кодом Хаффмана[1].
Далее привед
Код Шеннона
Далее приведен алгоритм кодирования по Шеннону:
Инициализации. Все буквы из алфавита записываются по убыванию вероятностей встречаемости в сообщениях. Каждой букве ставится в
Код Шеннона-Фано
Ниже приведен алгоритм кодирования по методу Шеннона-Фано:
Инициализации. Все буквы алфавита записываются в порядке убывания вероятностей.
Цикл. Всю совокупно
Код Гильбера-Мура
Далее приведен алгоритм кодирования по методу Гильбера-Мура.
Инициализация. Сопоставим каждой букве кумулятивную вероятность
Помехоустойчивое кодирование
Помехоустойчивые коды – это коды, позволяющие обнаружить и (или) исправить ошибки в кодовых словах, которые возникают при передачи по каналам связи. Эти коды строятся таким образом, что для
Коды с обнаружением ошибок
Рассмотрим простейший метод, принадлежащий к этой группе кодов и основанный на проверке на четность.
Схема кодирования: , то
Линейные блоковые коды
Линейным блоковым (n, k) кодом называется множество последовательностей длины
Коды Хэмминга
Код Хэмминга представляет собой один из важнейших классов линейных кодов, нашедших широкое применение на практике и имеющих простой и удобный для технической реализации алгоритм обнаружения и испра
Циклические коды
В отличие от кода Хемминга в циклическом коде используют математические операции не над векторами, а над многочленами. (Напомним, что произвольному вектору
Основные аспекты криптографии
Криптография – (до 70-ых годов) область научной и практической деятельности, связанной с разработкой, применением и анализом шифросистем; (в настоящее время) область науки, техники, практиче
Основные аспекты криптоанализа
Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сформулированное в XIX веке Д. А. Керкхофсом, состоит в том, что безопасность полностью опред
Шеноновские модели криптографии
На рис. 12 представлена общая схема симметричной криптосистемы.
Рис. 12. Схема симметричной крипто
Псевдослучайные последовательности
Случайные числа и их генераторы являются неотъемлемыми элементами современных криптосистем. Ниже приводятся конкретные примеры использования случайных чисел в криптологии:
1. Сеансовые и д
Система шифрования RSA
Данная криптосистема является шифрованием с открытым ключом. Алгоритм RSA[7] опирается на тот факт, что найти большие простые числа вычислительно легко, но разложить большое число на произведение д
Система шифрования Диффи-Хеллмана
Данный алгоритм[8] также является алгоритмом секретного обмена между абонентами ключом. Он основан на трудности вычисления дискретного логарифма.
Рассмотрим простейшую схему создания общег
Разложение на множители (факторизация)
Разложение на множители числа (например, ) является одной из древнейших проблем теории чисел. Приступая к факторизации числа, следует снача
Вычисление в поле Галуа
Напомним некоторые определения из алгебраических основ:
Поле – это множество
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Шеннон К. Теория связи в секретных системах. / В кн. Лекции по теории информации и кибернетике.–М.: ИЛ, 1963. Харин Ю.С., Берник В.И., Матвеев Г.В., Агиевич С.В. Матем
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
, называемое модулем.
,
для некоторого целого 
.
называют вычетом 
по модулю 
).
означает остаток от деления 
(например, 
). Эта операция называется приведением по модулю.
,
.
.
.
.
,
, 
имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
, равному любому делителю числа 
, где
.
, общие делители 24 и 6 – 2,3. Взаимно простое с 9 – это 2: 
. Тогда делим на 2 обе части сравнения: 
, иначе было бы неверно: 
.
при помощи свойства операции приведения по модулю: 
от деления на 
): 
.
.
Æ.
и 
«пробегает» полную систему вычетов по модулю 
, где 
делениями, при этом на одно деление автоматически попадают сравнимые между собой числа.
Новости и инфо для студентов