КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Лекция 2. Чтобы вычислить степень mn, где m – элемент некоторого кольца, а n – натуральное число, достаточно выполнить не более 2[log2n] умножений
Лемма. Чтобы вычислить степень mn, где m – элемент некоторого кольца, а n – натуральное число, достаточно выполнить не более 2[log2n] умножений.
Доказательство. В самом деле, пусть 2k-1 n <2k, k-1 =[log2n]. Тогда, записывая n в двоичной системе счисления, получим
Чтобы вычислить степень , можно поступить так. Сначала вычислить степени 1, . При этом достаточно выполнить k-1 умножений (возведений в квадрат). Затем некоторые из них следует перемножить. Их не более k-1. Итак, для вычисления степени потребуется не более 2(k-1) = 2[log2n] умножений.
Рассмотрим задачу отыскания целочисленного решения уравнения вида
ax - my=1 (1)
где (а,m)=1, a>0,m>0. Для решения этой задачи число a= обращают в конечную цепную дробь при помощи алгоритма Евклида:
Цепная дробь имеет вид:, а последовательности {Pn} и {Qn} числителей и знаменателей подходящих дробей к цепной дроби определяются рекуррентно:
Их вычисления удобно выполнять в виде таблицы:
Но известно, что
Таким образом,
А так как (a,m)=1,то Pk=a, Qk= m.Поэтому
другими словами, пара <x,y>, где
является целочисленным решением уравнения (1).
Решения сравнения первой степени.
Чтобы найти решение сравнения a*xº1(mod m), где (a,m)=1, обычно используют алгоритм Эвклида, и тогда xº(1)k-1 Qk-1(mod m), где Qk-1 – знаменатель предпоследней проходящей дроби разложения в цепную дробь, теорема Ферма – Эйлера, которая утверждает, что если (a,m)=1, то Пример. Решить сравнение.
Криптосистема без передачи ключей,криптосистема с открытым ключом. Криптосистема без передачи ключей. Пусть абоненты А, В, С,... условились организовать секретную переписку между собой. Для этой цели они выбирают достаточно большое простое число p и такое, что р -1 хорошо разлагается на не очень большие простые множители. Если среди множителей такого числа кратных нет, то число р - 1 называют евклидовым. Каждый из абонентов независимо один от другого выбирает случайное число, натуральное, взаимно простое с числом р- 1: А, В, С,... - абоненты; а, Ь, с,... - выбранные ими случайные числа. Далее, абонент А находит число a из условия:
абонент В находит число b из условия: (2.3)
a, а - секретные ключи абонента А; b, b — секретные ключи абонента В и т.д. Пусть абонент А решает послать сообщение m абоненту В; можно предполагать, что 0 < m < р- 1. Тогда он сначала зашифровывает это сообщение своим первым секретным ключом, находит
и отправляет абоненту В. Абонент В, в свою очередь, зашифровывает вновь это сообщение также своим первым ключом:
и пересылает его обратно абоненту A. Абонент А, получив обратно свое дважды зашифрованное сообщение, шифрует его же в третий раз своим вторым ключом:
(2.6)
и вновь отправляет его абоненту В. Последний расшифровывает эту шифротелеграмму при помощи своего второго ключа:
В самом деле, из сравнений (2.4), (2.5) и (2.6) имеем
где В силу (2.2) и (2.3) Поэтому m4= m(mod p), а так как каждое из них положительно и меньше р, то
Пример. Предположим, что абоненты А и В решили установить между собой скрытую связь без передачи ключей. Они выбрали для этого простое число p = 23, далее абонент A выбирает случайным образом число а = 5, абонент В также случайно выбирает число Ь = 7.
Затем А, решая сравнение 5 • х º 1(mod j(23)), находит х =9, анало
Второй абонент, получив это сообщение, шифрует его также своим первым ключом 7 и отправляет его обратно абоненту А:
Абонент А вновь шифрует полученное сообщение своим вторым ключом 9 и отправляет новое шифрованное сообщение абоненту В:
Получив это сообщение, абонент В расшифровывает его при помощи своего второго ключа 19:
И так как 0 < 17 < 23, то m = 17
Дата добавления: 2014-01-13; Просмотров: 455; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |