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

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

Мультипликативная функция

Мультипликативная функция - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Имеем Два Натуральных Числа A И B, Если Они Взаимно Просты, Т...

 

Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по формуле:

 

 

т.е. при больших a и b, эта формула позволяет уменьшить вычислительную сложность.

Но если числа a и b не взаимно простые, то вычисления проводятся по обычной формуле.

Пример:

 

a=60 b=11. 60 и 11 – взаимно простые.

 

 

Как мы уже выяснили, для 60 число взаимно простых чисел равно 16, а для

 

11 равно 10.

 

т.е. .

 

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

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

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

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

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

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

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

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

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

Алгоритм Евклида
  Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Алгоритм рае кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

Для возведение натуральных чисел по модулю в большие степени
    Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.     Имеется целое число

Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида   y = a x mod m , (1.1)   где a ÎN - основание степени,  

Сравнимость по модулю. Модулярная арифметика
    Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.   Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив

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

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
  Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2 xn ≡ a mod p – квадратичный выч

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

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9]
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

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 На основе этих двух операций получаем про

М-последовательности. ГПСЧ типа ЛРС1
  Опр ед ел ени е. Последовательностью над полем   GF ( p)   будем   назы

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Алгоритм асимметричного шифрования RSA
  Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

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

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