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

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

Простые числа

Простые числа - раздел Компьютеры, Методы и средства защиты компьютерной информации   Едва Освовив Четыре Арифметических Действия, Люди Стали Интер...

 

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

Допустим, что простых чисел существует лишь конечное количество. Обозначим все эти простые числа p1, p2, ..., pk и составим число N = p1p2...pk + 1. Это число по предположению (ибо даже самое большое простое число pk меньше N) не может быть простым. Следовательно, оно должно раскладываться на множители:

p1p2...pk + 1 = q1q2...qm

Ни одно из чисел q1, q2, ..., qm не может совпасть ни с одним из чисел p1, p2, ..., pk, ибо в случае qi = pj должна была бы и правая часть равенства

p1p2...pkq1q2...qm = –1

делиться на это qi = pj, что невозможно, т. е. q1, q2, ..., qm – еще какие-то простые числа, хотя мы считали, что их всего k.

Такое вычисление на самом деле довольно часто приводит к новым простым числам. Обычно их называют факториальными. Рекорд – это число (около 8000 цифр)

2´3´5´...´18523+1.

Теорема (основная теорема арифметики). Всякое целое число a, большее 1, представляется в виде произведения степеней простых сомножителей, причем это разложение единственно (с точностью до перестановки мест сомножителей), т. е. , где a1, a2, ..., ak ³ 0.

Вопрос о том, как часто простые числа встречаются в натуральном ряду и как они распределены среди натуральных чисел, оказался очень сложным. Изучение таблиц простых чисел показывает, что в натуральном ряду есть участки, где простые числа располагаются гуще. Есть даже числа, которые находятся совсем близко друг от друга, как, например, 2 и 3, 3 и 5, 191 и 193, 2711 и 2713. Такие пары чисел называются близнецами. До сих пор неизвестно, конечно или бесконечно число пар близнецов. Самая большая (на сегодняшний день) пара близнецов была открыта в 1995 году: это числа 242206083´238880–1 и 242206083´238880+1. Однако, существуют сколь угодно длинные отрезки натурального ряда, в которых нет ни одного простого числа. Например, среди последовательных чисел k!+2, k!+3, ..., k!+k нет ни одного простого.

Важными характеристиками расположения простых чисел в натуральном ряду служат величины: p(n) – число простых чисел, не превосходящих n, и отношение – средняя плотность простых чисел среди первых n натуральных. Изучение таблиц простых чисел показало, что, двигаясь по натуральному ряду, мы будем встречать простые числа все реже. Эйлер обосновал это наблюдение, доказав, что . Иногда это выражают словами: “Вероятность того, что наугад выбранное число – простое, равна нулю”. Можно доказать, что простые числа располагаются все же гуще квадратов натуральных чисел.

Но все эти результаты очень мало говорят о самом числе p(n). Математикам хотелось получить для p(n) какую-нибудь достаточно простую приближенную формулу. Первая гипотеза о величине p(n) была сделана независимо французским математиком А. Лежандром и К. Гауссом около 1800 г. Она заключалась в том, что . Однако доказать это утверждение улалось лишь 100 лет спустя. Функция p(n) называется функцией Чебышева.

Определение. Функция Эйлера j(n) определяется для всех целых положительных n и представляет собою количество чисел ряда 1, 2, ..., n–1, взаимно простых с n.

Пусть – каноническое разложение числа n. Вычеркнем из ряда 1, 2, ..., n все числа, которые делятся на p1. Таких чисел будет . Останется чисел, не делящихся на p1. Теперь из оставшихся чисел выбросим все числа, делящиеся на p2. Их будет

.

Останется

.

Продолжая дальше выбрасывать числа, делящиеся на p3, p4, ..., pk придем к формуле

,

или также

.

В частности, будем иметь

j(pa) = papa–1, j(p) = p – 1,

где p – простое число.

Приведем без доказательства одно важное свойство функции Эйлера: при взаимно простых n1 и n2 имеет место равенство

j(n1n2) = j(n1)j(n2).

Рассмотрим некоторые простые числа специального вида.

Простые числа Мерсенна являются простыми числами вида

M(p) = 2p – 1,

названные так в честь французского монаха Марена Мерсенна, жившего в начале XVII века. Любой математик быстро сообразит, что M(p) бывает простым только тогда, когда само число p – простое, т. к. 2uv – 1 делится на 2u – 1. А верно ли обратное – то есть для любого ли простого p число M(p) будет простым? К сожалению нет. Например, число M(11) – составное: M(11) = 2047 = 23´89.

Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел M(p) для различных простых чисел p. Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение.

Сам Мерсенн нашел несколько первых простых чисел такого вида и сделал предположение о следующих. Несмотря на то, что его предположение оказалось частично ошибочным, оно привлекло к себе внимание лучших математиков того времени. В 1750 году Леонард Эйлер установил, что число M(31) является простым. Это число оставалось самым большим из известных простых чисел более ста лет. В 1876 году французский математик Лукаш установил, что число M(127) является простым числом. Для проверки на простоту чисел Мерсенна был разработан специальный алгоритм – тест Лукаша–Лемера[4]. Именно благодаря этому алгоритму стало возможным проверять простоту чисел, содержащих многие тысячи десятичных цифр!

Интерес к чмслам Мерсенна тесно связан с так называемыми совершенными числами, – числами, равными сумме своих делителей (исключая само число): 6 = 1+2+3, 28 = 1+2+4+7+14. А именно: если число M(p) – простое, то 2p–1´M(p) – совершенное.

До сих пор неизвестно, конечно или бесконечно количество простых чисел Мерсенна.

Существует еще один тип простых чисел с большой и интересной историей. Они были впервые введены французским юристом Пером Ферма (1601–1665), который прославился своими выдающимися математическими работами. Он также занимался поиском больших простых чисел. Например, Ферма установил, что числа 21 + 1, 22 + 1, 24 + 1, 216 + 1 – простые. В письме Мерсенну, написанном в 1640 г. Ферма выдвинул предположение, что – всегда число простое, но сообщил, что не в состоянии определить, является число 4294967297 = 232 + 1 простым или нет. Мы можем вычислить , выполнив для этого 32 опрерации возведения в квадрат по модулю 232 + 1, в результате получится 3029026160; следовательно, (согласно собственной теореме Ферма, которую он доказал в том же 1640 г.!), 232 + 1 не есть простое число. Это доказательство не дает абсолютно никакой информации относительно множителей, а только дает ответ на поставленный Ферма вопрос. Позднее Эйлер определил, что это число имеет делитель равный 641. Сейчас числа вида

называются числами Ферма. Первые четыре числа Ферма: 5, 17, 257, 65537 простые, но уже пятое число – F(5) = 232 + 1, как показал Эйлер, является составным. Других простых чисел Ферма так и найдено.

 

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

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

Методы и средства защиты компьютерной информации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги