Главная » Просмотр файлов » А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии

А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 3

Файл №1127102 А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии) 3 страницаА.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102) страница 32019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Но (ac,b)\b (ac,b)\(c,b).

С другой стороны, (c,b)\ac, (c,b)\b. (c,b)\(ac,b).

Таким образом, числа (ac,b) и (c,b). взаимно делят друг друга (ac,b)=(c,b).

4) (a,b)=1, b\ac b\c.

Доказательство:

Из теоремы №1 о НОД в силу b\ac, (ac,b)=b.

из свойства НОД № 3 b=(c,b)и тогда из теоремы №1 о НОД b\c.

5) Если (ai, bj)=1 для , ( , )=1.

Доказательство:

имеем ( , ) = ( , ) = ( , ) = … = .

Аналогично, используя полученное соотношение,

( , ) = ( , ) = … = ( , ) = 1.

1.3 НОК (наименьшее общее кратное)

Если a1\b, a2\b, … , an\b, то b называется общим кратным чисел a1,…,an. Наименьшее положительное общее кратное чисел a1,…,an называется их наименьшим общим кратным (НОК).

Пусть НОД(a,b)=d, тогда можно записать a=da1, b=db1, где (a1,b1)=1.

Пусть a\M, b\M M=ak для некоторого целого k, и тогда число – целое. Но, поскольку (a1,b1)=1, то b1\k , и тогда k=b1t для некоторого , и

. *

Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных.

При t=1 имеем M=НОК(a,b).

Формулой M = НОК(a,b)∙t можно представить все общие кратные чисел a и b. ( ).

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

Числа a1,…,an называются взаимно простыми, если НОД(a1,…,an)=1, попарно простыми, если , НОД(ai,aj)=1.

Если числа попарно a1,…,an простые, то они взаимно простые. Обратное неверно.

Число p называется простым, если оно имеет лишь два делителя – “1” и р.

Число “1” делится только на себя, и не является ни простым, ни составным, а занимает особое место в теории чисел.

Число а>1 имеющее более двух делителей, называется составным.

Утверждение 1

Наименьший не равный единице делитель числа a: , >1, является простым числом.

Доказательство:
Пусть q: q>1, q\a – наименьший делитель а. Если бы q было составным, то нашлось бы число q1>1: q1\q, и тогда для некоторого целого k выполнялось бы q=kq1 a=qt=q1kt q1\a, q1<q (то есть нашелся делитель числа a, который меньше q) q – не наименьший делитель числа a. Пришли к противоречию с условием теоремы. Предположение неверное, следовательно верно обратное. q – простое число.

Утверждение 2

p – наименьший делитель составного числа а, p≠1 .

Доказательство:

Представим a в виде a=pa1. Поскольку p – наименьший делитель числа a, то a1p ap2 в силу монотонности квадратичной функции на положительной полуоси, p .

Теорема Евклида (о простых числах) №1

Простых чисел бесконечно много.

Доказательство:

Пусть простых чисел ровно k штук, и p1,…,pk – все простые числа.

Возьмем n=p1p2∙…∙pk+1. По предположению, n – составное число, т.к. n> , существует простое число d: d\n.

Но очевидно, исходя из вида числа n, что , получили противоречие с тем, что p1,…,pk – все простые числа.

Теорема Евклида (о простых числах) №2

в числовом ряду (1, 2, 3, …) существует k подряд идущих составных чисел.

Доказательство:

Возьмем m=k+1.

m!+2, m!+3,…, m!+mсоставные числа, и их ровно k штук.

Решето Эратосфена

Решето Эратосфена используется для составления таблицы простых чисел, меньших или равных наперед заданного натурального числа N.

  1. Выписываем числа 1 2 3 … N

  2. Первое число, которое больше, чем 1, есть 2. Двойка делится только на 1 и 2, т.е. является простым числом.

Вычеркиваем из ряда (как составные) все числа, кратные 2, кроме самой двойки.

  1. Второе невычеркнутое число есть 3. Оно не делится на 2, иначе оно оказалось бы вычеркнутым, значит 3 делится только на 1 и 3, значит 3 – простое число.

Вычеркиваем из ряда все числа, кратные 3.

  1. Следующее невычеркнутое число есть 5. Оно простое, так как не делится ни на одно число, меньшее самого себя, иначе оно было бы вычеркнуто. Вычеркиваем все числа, кратные 5, кроме самой пятерки.

Этот процесс продолжаем далее для всех невычеркнутых чисел.

Когда этим способом вычеркнуты все числа, меньшие p (p – простое), то все невычеркнутые числа, меньшие p2, будут простыми.

Действительно, всякое составное а<p2 уже вычеркнуто, как кратное его наименьшего делителя d: a=da1 который d <p (по утверждению 2).

Тогда следуют правила:

  1. Числа, кратные р, вычеркиваются, начиная с p2.

  2. Составление таблицы простых чисел, меньших или равных N, закончено, как только вычеркнуты все кратные простых, меньших или равных

Пример: N=50 .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

1.5. Единственность разложения на простые сомножители.

Утверждение 1.

Любое целое число a либо взаимно просто с данным простым р, либо р\а.

Доказательство:

, p – простое число, выполняется (a,p)\p. Тогда в силу простоты p, либо (a,p)=p, либо (a,p)=1. В первом случае р\а, во втором a взаимно просто с р. Что и требовалось доказать.

Теорема (Основное свойство простых чисел)

Если a1,…,ak Z, p\( a1∙…∙ak) : p\ai.

Доказательство:

В силу утверждения 1, либо (ai,p)=1, либо (ai,p)=p. Если бы выполнялось (ai,p)=1 то выполнялось бы ( a1∙…∙ak, p)=1, и тогда p не делило бы (a1∙…∙ak). Получили противоречие с условием теоремы : p\ai.

Теорема (О единственности разложения на произведение простых чисел)

, а>1 существует единственное разложение a=p1p2∙…∙pn, где , рi – простое .

Доказательство:

Действительно, обозначая буквой p1 наименьший (простой) делитель а, имеем a=p1a1 Если a1>0, то, обозначая p2 наименьший (простой) делитель числа a1, имеем a1=p2a2 и т.д., пока не придем к an=1 для некоторого n (поскольку ряд a1, a2, …, an - убывающий ряд натуральных чисел, то рано или поздно мы придем к единице).

Тогда a=p1p2∙…∙pn. Показали существование разложения на простые сомножители. Теперь докажем единственность.

Предположим, что для того же самого а существует второе разложение на простые сомножители a=q1q2∙…∙qs, и, не нарушая общности, предположим, что sn. Тогда

p1p2∙…∙pn = q1q2∙…∙qs *

В силу основного свойства простых чисел, q1\( p1p2∙…∙pn) i: q1\pi. Не нарушая общности, предположим, что i=1 q1\p1. В силу простоты чисел p1, q1, получим p1=q1. Сократив обе части равенства (*) на q1, получим

p2∙…∙pn = q2∙…∙qs,

p1=q1

Повторив рассуждения для q2, получим

p3∙…∙pn = q3∙…∙qs,

p1=q1, p2=q2

И т.д. В итоге получим

1=qn+1∙…∙qs,

p1=q1, p2=q2, … , pn=qn

Отсюда qn+1=1, …, qs=1. То есть оба разложения на простые сомножители тождественны.

В разложении числа на простые сомножители некоторые из сомножителей могут повторяться. Обозначая p1,…, pk различные из них, а α1,…, αk – кратности их вхождения в разложение, получим каноническое разложение числа а:

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

Теорема (о делителях числа)

Пусть – каноническое разложение числа a. Тогда все делители а имеют вид

, где 0≤β1α1, 0≤β2α2, …, 0≤βkαk.

Доказательство:

Пусть q\a a представимо в виде a=dq, тогда все простые делители числа d входят в каноническое разложение числа а с показателями, не меньшими тех, с которыми они входят в каноническое разложение числа а.

Следствие 1

Количество различных делителей числа есть .

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

Следствие 2

НОД(a1,…,an), где ( ), есть , где ( ).

Пример.

a1=2∙3∙52=150, a2=22∙5∙7=140, a3=23∙5=40.

p1=2, p2=3, p3=5, p4=7.

a1= , a2= , a3= .

НОД(a1,a2,a3)= =2∙5=10.

Следствие 3

Совокупность общих делителей a1,…,an совпадает с совокупностью делителей НОД(a1,…,an).

Следствие 4

НОК , где ,

Пример.

НОК(150,140,40)=

Следствие 5

Если a1,…,an – попарно простые числа, то НОК(a1,…,an)= a1∙…∙an

Следствие 6

Совокупность общих кратных чисел a1,…,an совпадает с совокупностью кратных их наименьшего общего кратного.

Доказательства следствий 1–6 предоставляется читателю в качестве упражнения. Отыскать эти доказательства можно в [5] (Виноградов, «Основы теории чисел»).

1.6. Асимптотический закон распределения простых чисел.

Решето Эратосфена отыскивает все простые числа от 1 до N. Однако при большом N поиск простых чисел таким способом отнимает много времени. Современная практическая криптография требует использования больших простых чисел – в некоторых стандартах используются простые числа размером порядка 1024 бита.

По понятным причинам, невозможно организовать поиск таких больших простых чисел при помощи решета Эратосфена. В настоящее время разработано несколько вероятностных и детерминированных тестов на простоту. Эти тесты определяют, является ли наугад выбранное число простым или составным. Далее мы изучим такие вероятностные тесты, как тест Ферма, Соловея-Штрассена, Миллера-Рабина.

Характеристики

Тип файла
Документ
Размер
2,98 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее