рефераты конспекты курсовые дипломные лекции шпоры

Раздел Компьютеры
/
Сравнения с одним неизвестным

Реферат Курсовая Конспект

Выберите учебное заведение

Сравнения с одним неизвестным

Сравнения с одним неизвестным - раздел Компьютеры, МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ КОМПЬЮТЕРНОЙ ИНФОРМАЦИИ Числа, Равноостаточные, Или, Что То Же Самое, Сравнимые По Мо...

Числа, равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа.

Соответственно m различным значениям r имеем m классов чисел по модулю m.

Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом.

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Чаще всего в качестве полной системы вычетов употребляют наменьшие неотрицательные вычеты 0, 1, ..., m – 1.

Теорема 1. Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Доказательство. Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, так как их m, т. е. столько же сколько и классов, то в каждый класс наверно попадет по одному числу.

Теорема 2. Если D(a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b – любое целое, тоже пробегает полную систему вычетов по модулю m.

Доказательство. Действительно, чисел ax + b будет столько же сколько и чисел x, т. е. m. Согласно предыдущей теореме остается, следовательно, только показать, что любые два числа ax₁ + b и ax₂ + b отвечающие несравнимым x₁ и x₂, будут сами несравнимы по модулю m. Но допустив, что ax₁ + b º ax₂ + b (mod m), мы придем к сравнению ax₁ º ax₂ (mod m), откуда, вследствие D(a, m) = 1, получим x₁ º x₂ (mod m), что противоречит предположению о несравнимости чисел x₁ и x₂.

Рассмотрим сравнение такого общего вида:

f (x) º 0 (mod m); f(x) = axⁿ + a₁xⁿ^–1 +...+ a_n. (1)

Если a не делится на m, то n называется степенью сравнения. Решить сравнение – значит найти все значения x, ему удовлетворяющие. Два сравнения, которым удовлетворяют одни и те же значения x, называются равносильными.

Если сравнению (1) удовлетворяет какое-либо x = x₁, то (следствие из теоремы, касающейся свойств сравнений) тому же сравнению будут удовлетворять и все числа, сравнимые с x₁ по модулю m: x º x₁ (mod m). Весь этот класс чисел считается за одно решение. При таком соглашении сравнение (1) будет иметь столько решений, сколько вычетов полной системы ему удовлетворяет.

Пример. Сравнению

x⁵ + x + 1 º 0 (mod 7)

среди чисел 0, 1, 2, 3, 4, 5, 6 полной системы вычетов по модулю 7 удовлетворяют два числа x = 2 и x = 4. Поэтому указанное сравнение имеет два решения:

x º 2 (mod 7), x º 4 (mod 7).

Из сравнений с одним неизвестным в дальнейшем будем рассматривать лишь простейшие, а именно сравнения первой степени, которые перенесением свободного члена (с обратным знаком) в правую часть можно привести к виду

ax º b (mod m). (2)

Рассмотрим вопрос о числе решений сравнения (2). Ответ на этот вопрос дают три нижеследующие теоремы.

Теорема. Если D(a, m) = 1, то сравнение (2) имеет единственное решение.

Доказательство. Наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю m, то ax пробегает полную систему вычетов (теорема 2). Следовательно, при одном и только одном значении x, взятом из полной системы ax будет сравнимо с b.

Теорема. Если D(a, m) = d и d не делит числа b, то сравнение (2) не имеет решений.

Доказательство. Это непосредственно следует из свойства 9 сравнений, хотя можно доказать следующим образом. Допустим, чтосуществует x₀, удовлетворяющее этому сравнению:

ax₀ º b (mod m).

Это можно записать в виде уравнения

ax₀ – b = mt Þ ax₀ – mt = b, где t – целое.

Здесь левая часть делится на d, а правая не делится, что невозможно.

Теорема. Если D(a, m) = d и b кратно d, то сравнение (2) имеет d решений. Все эти решения образуют один класс по модулю .

Доказательство. Пусть a = a₁d, b = b₁d, m = m₁d. Тогда сравнение (2) будет равносильно такому (по сокращении на d) a₁x º b₁ (mod m₁), в котором уже D(a₁, m₁) = 1, и потому оно будет иметь одно решение по модулю m₁. Пусть x₁ – наименьший неотрицательный вычет этого решения по модулю m₁, тогда все числа x, образующие это решение, найдутся в виде

x º x₁ (mod m₁). (3)

По модулю же m числа (3) образуют не одно решение, а больше, именно столько решений, сколько чисел (3) найдется в ряде 0, 1, 2, ..., m – 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (3):

x₁, x₁ + m₁, x₁ + 2m₁, ..., x₁ + (d–1)m₁,

т. е. всего d чисел (3); следовательно, сравнение (2) имеет d решений.

Рассмотрим один частный вид сравнения первой степени:

ax º 1 (mod m),

где D(a, m) = 1. Оно равносильно уравнению ax = 1 + mt Þ ax – mt = 1 Þ ax + mp = 1. Теперь нам необходимо подобрать числа x, p так, чтобы выполнялось это уравнение. А это позволяет сделать, рассматриваемый в следующем параграфе, обобщенный алгоритм Евклида.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ КОМПЬЮТЕРНОЙ ИНФОРМАЦИИ

Факультет электронной техники... Кафедра Автоматизированные системы обработки информации и управления...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Сравнения с одним неизвестным

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Актуальность защиты систем обработки информации
В современном компьютерном сообществе атаки на информацию стали обыденной практикой. Злоумышленники используют как ошибки в написании и администрировании программ, так и методы соци

Угрозы безопасности компьютерных систем
Под угрозой безопасности вычислительной системы понимаются воздействия на систему, которые прямо или косвенно могут нанести ущерб ее безопасности. Разработчики треб

Наиболее распространенные методы взлома компьютерных систем
1.3.1. Комплексный поиск возможных методов взлома Часто злоумышленники проникают в систему не напрямую, «сражаясь» с системами шифрован

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

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

Получение пароля на основе ошибок в реализации
Следующей по частоте использования является методика получения паролей из самой системы. Однако, здесь уже нет возможности дать какие-либо общие рекомендации, поскольку все методы а

Социальная психология и иные способы получения паролей
Иногда злоумышленники вступают и в прямой контакт с лицами, обладающими нужной им информацией, разыгрывая довольно убедительные сцены. «Жертва» обмана, поверившая в реальность расск

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

Краткие сведения о криптоанализе
Криптоанализ как наука выходит за рамки данного курса, однако знание некоторых его положений необходимо для глубокого понимания криптографии. Главным действующим лицом в кр

Мера стойкости шифра
Шифром называется пара алгоритмов (E и D), реализующих каждое из указанных выше преобразований. Секретность второго из них делает данные недоступными

Необходимое условие абсолютной стойкости шифра
Естественно, основной вопрос, который интересовал криптографов, это существуют ли на практике абсолютно стойкие шифры. Специалистам было интуитивно понятно, что они существуют, и пр

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

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

Базовая идея блочного шифра
Отправной точкой в реализации рассматриваемого подхода является идея вырабатывать гамму для зашифрования сообщения … из самого сообщения! Однако сделать это непосредственно невозмож

Шифр простой замены
Для того, чтобы блочная схема шифрования была устойчива к криптоанализу, она должна обладать свойствами перемешивания и рассеивания. Это означает, что каждый бит исходного текста до

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

Гаммирование
Предложенная в предыдущем разделе процедура шифрования по методу простой замены с использования датчика псевдослучайных чисел может быть слегка изменена, что освободит ее от ряда не

Гаммирование с обратной связью
При синтезе алгоритма блочного шифрования мы уже сталкивались с идеей вырабатывать гамму для шифрования очередного блока данных с использованием одного или нескольких предыдущих бло

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

Сравнения и их свойства
Мы будем рассматривать целые числа в связи с остатками от деления их на целое положительное m, которое назовем модулем (слово “модуль” происходит от латинско

Вычисление степеней, возведение сравнений в степень
Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому обсудим интересную задачу эффективного вычисления xn по заданным x и

Наибольший общий делитель
Если u и v – целые числа, не оба рвные нулю, то их наибольшим общим делителем D(u, v) называется наибольшее целое число, на которое делятся без ос

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

Теоремы Эйлера и Ферма
Теорема (Эйлера). При m > 1 и D(a,m) = 1 имеем aj(m) º 1 (mod m).

Однонаправленные функции
Развитие криптографии в XX веке было стремительным, но неравномерным. Анализ истории ее развития как специфической области человеческой деятельности выделяет три основных периода.

Алгоритм RSA
Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авто

Практическое использование алгоритма RSA
Для алгоритмов, основанных на открытых ключах, существует ряд математических проблем, которые не всегда учитываются при построении криптосистемы. К ним можно отнести выбор начальных

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

Электронная подпись
В чем состоит проблема аутентификации данных? В конце обычного письма или документа исполнитель или ответственное лицо обычно ставит свою подпись. Подобное действие обычно преследуе