Свойства делимости целых чисел - Лекция, раздел Математика, Материалы лекций Математические основы криптологии
Два Числа A И B Называются Взаимно Простыми Если Их Нод = 1...
Два числа a и b называются взаимно простыми если их НОД = 1
(a1,a2,….,an)= НОД
(a1,a2) = d1
(a3,d1) = d2
…………..
(dn-3,dn-1) = dn
a1*a2= k*d
Теорема разложения целых чисел (главная теорема арифметики)Любое составное число m можно однозначно представить в виде произведения простых сомножителей p, m = p1*p2*…..*pk
Эта теорема имеет большое прикладное значение в криптографии.
Обозначения:
m – составное число
p - простое
Составное число может раскладываться на простые, при этом могут быть две формы:
Кратность указывается с помощью верхнего индекса 720 = 24*32*5 -
такая форма носит название – каноническое разложение на простые сомножители.
Это позволяет при большем числе кратных сомножителей достаточно компактно записать разложение.
С помощью такого «школьного» алгоритма число с большим
количеством десятичных знаков можно раскладывать годами.
Это одна из сложных математических задач на которой основаны алгоритмы шифрование/расшифрования с помощью открытого ключа. При секретном ключе данная задача не используется. Вообще шифрование с открытым ключом основано на ряде математически сложных задач. Задач, для которых быстродействующие алгоритмы пока не придуманы. На этом и основана криптостойкость. Эта криптостойкость носит название практической криптостойкости, т.к. как только будут найдены другие быстродействующие алгоритмы разложение, эти алгоритмы потеряют свою актуальность. В перспективе таким возможным алгоритмом может стать алгоритм на основе квантовой физики. Там все процессы идут параллельно и независимо от тако насколько большое число все делается достаточно быстро.
Одним из алгоритмов основанных на решение сложных математических задач, является алгоритм RSA. Этот алгоритм мы рассмотрим в одной из следующих лекций и немножко под другим углом.
Применение этой теоремы это – например для нахождение НОД. Т.е зная разложение, два числа, допустим a и b такие что:
Примечание: При получение разного числа сомножителей можно дописать так называемые «фиктивные» сомножители. н-р:
мы можем найти НОД по формуле:
От каждого разложение берется пара сомножителей, выбирается по показателям.
из каждой пары сомножителей выбирается сомножитель с минимальным показателем.
Пример
Т.е. 720= 24*32*5,
а 90= 2*32*5
Берем минимальные показатели :
- т.е. число 90 является НОД(d) чисел 90 и
720.
Аналогично НОК :
- т.е. число 720 является НОК(k) чисел 90 и 720.
Другая сфера приложения это н-р: Имеем некоторое большое число и имеем его разложение и на основе этого надо найти все его делители .
Если кратность в разложение есть то удобно использовать определенный способ нахождения всех делителей.
В общем случае когда составное число раскладывается по канонической формуле все делители можно найти по такой формуле (эта формула тоже обосновывается теоремой)
- мы имеем разложение
…………….
В нашем случае (про 720)
и подставляя всевозможные вариации этих значений мы и получим все делители.
т.е. d = 1,2,4,8,16…………
в нашем случае будет 30 делителей
Еще один вариант приложения разложения. По разложения можно найти сумму всех делителей ()
Принято обозначать сумму всех делителей нашего числа акак
В М Захаров... Материалы лекций... Математические основы криптологии...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Свойства делимости целых чисел
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной
криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от
Алгоритм Евклида
Алгоритм Евклида дает правило вычисления наибольшего общего делителя
(НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное
Получение простых чисел.
По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме.
Задача получение простых чисел во многом зависит от того как с
Проверка простоты чисел Мерсенна
Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.
Задача для чисел Мерсенна - поиск в ряду э
Алгоритм Бухштаба
Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2
Алгоритм Ферма
Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который
Функция Эйлера
Имеется целое, положительное число m. Оно может быть как составным, так и простым.
Функцию Эйлера принято обозначать, практически во всех учебниках как:
Мультипликативная функция
Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо
Числовая функция
Это функция устанавливающая целую часть от некоторого рационального числа
[a] – обозначение
может быть как положительное, так и отрицательное число
Сравнимость по модулю. Модулярная арифметика
Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.
Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив
Свойства операций сравнения
В криптографии существуют шифры и по простому модулю и по составному модулю.
Нужно знать когда применять простой модуль, а когда состав
Кольца и поля
Алгебраические структуры с двумя бинарными операциями - сложение и умножение.
Определение 1.7. Множество S называется кольцом, е
Характеристика поля
Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.
Вычисление обратных элементов
В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a:
a-1 = 1/a или a? a-1 = 1.
Расширение полей
Рассмотрим, какова связь полей GF(p) и GF( p n ).
Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на
Pound; b£ n-1
Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:
(1) bn-1≡ 1(mod n),
Числа Кармайкла
Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».
Заметим
Процедура получения устойчивых простых чисел
1. Генерируются простые числа s,t
2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t
На основе этих двух операций получаем про
Алгоритм асимметричного шифрования RSA
Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и
Раунд преобразования алгоритма RIJNDAEL
RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
720 2
Это позволяет при большем числе кратных сомножителей достаточно компактно записать разложение.
Применение этой теоремы это – например для нахождение НОД. Т.е зная разложение, два числа, допустим a и b такие что:
мы можем найти НОД по формуле:
От каждого разложение берется пара сомножителей, выбирается по показателям.
из каждой пары сомножителей выбирается сомножитель с минимальным показателем.
Пример
- т.е. число 90 является НОД(d) чисел 90 и
Аналогично НОК :
- т.е. число 720 является НОК(k) чисел 90 и 720.
- мы имеем разложение
В нашем случае (про 720)
)
Для нашего примера это будет выглядеть так:
Новости и инфо для студентов