Лабораторная работа №7 Тақырыбы: Некоторые алгоритмы расчета: Алгоритм Евклида. Обобщенный алгоритм Евклида. Алгоритм ранжирования
жүктеу/скачать 37,17 Kb.
|
Лабораторная работа 7
- Бұл бет үшін навигация:
- Определение 2.
| Пример 2. Пусть . (1)- найдите x и y, которые удовлетворяют
Поясним полученный рисунок. Сначала цифры пишутся в строке (28.1.0) и в строке (19,0,1) (это первые две строки на схеме). Затем рассчитывается линия T (третья линия на этой диаграмме). Теперь две линии на чертеже принимаются за , а третья линия принимается за , и снова вычисляется Т (это четвертая линия на чертеже). Мы продолжаем этот процесс до тех пор, пока первый элемент строки V не станет нулем. Тогда ответ задачи находится в строке перед последней строкой диаграммы. В нашем случае НОД(28,19)=1, x=-2,y=3. Проверим: 28*(-2)+19*3=1. Покажем еще одно важное подтверждение обобщенного алгоритма Евклида. Для чисел c и d, данных во многих задачах криптографии (1) необходимо найти число d Определение 2. Число d, удовлетворяющее равенству (1), называется обращением c по модулю m и обозначается как . Такое обозначение естественно для инверсии, поскольку теперь мы можем записать (1) как . То есть - умножение соответствует делению на c при расчете по модулю m. Аналогично, любой отрицательный показатель степени может быть введен в расчет по модулю m. (1) теңдігін қанағаттандыратын саны ның модулі бойынша инверсиясы деп аталады және түрінде белгіленеді. Инверсия үшін мұндай белгілеу табиғи болып табылады, себебі, енді біз (1)-ді түрінде жаза аламыз. Яғни – көбейту модуль бойынша есептеуде ға бөлуге сәйкес келеді. Осыған ұқсас, модуль бойынша есептеуде кез келген теріс дәрежені енгізуге болады. . Мысалы 3. , поэтому 4 является обратным числу 3 по модулю 11. . номер можно узнать двумя способами: , При расчете вторым методом мы использовали равенство . На самом деле . Покажем, что инверсию можно вычислить с помощью обобщенного алгоритма Евклида. равенство для некоторого целого числа k указывает на то, что будет Учитывая, что c и m — взаимно простые числа, это равенство (2) можно записать как И это полностью соответствует (1), только здесь переменные надо обозначить по-другому. Это связано с тем, что для вычисления c^(-1) mod m, т. е. для нахождения числа d, для решения уравнения (2) следует использовать только обобщенный алгоритм Евклида. Обратите внимание, что нас не интересует значение k-переменной, поэтому вторые элементы строк U,V,T можно опустить. При этом, если d-число отрицательное, то к нему следует добавить m-число, поскольку по определению число a mod m берется из множества {0,1,..,m-1 }. Пример 4. Вычислим . Воспользуемся формулой для записи расчета, использованной в примере 2: Что мы получаем, и , т.е., . Проверим результат: . Одним из наиболее важных методов криптографии с открытым ключом является метод получения степеней по модулю. Опишем этот алгоритм в форме, удобной для прямой программной реализации. Название алгоритма указывает на то, что биты показателя степени считаются справа налево, то есть от меньшего к большему.. жүктеу/скачать 37,17 Kb. Достарыңызбен бөлісу:
|