Лабораторная работа №7 Тақырыбы: Некоторые алгоритмы расчета: Алгоритм Евклида. Обобщенный алгоритм Евклида. Алгоритм ранжирования

Поясним полученный рисунок. Сначала цифры пишутся в строке (28.1.0) и в строке (19,0,1) (это первые две строки на схеме). Затем рассчитывается линия T (третья линия на этой диаграмме). Теперь две линии на чертеже принимаются за , а третья линия принимается за , и снова вычисляется Т (это четвертая линия на чертеже).

необходимо найти число d
Определение 2. Число d, удовлетворяющее равенству (1), называется обращением c по модулю m и обозначается как . Такое обозначение естественно для инверсии, поскольку теперь мы можем записать (1) как . То есть - умножение соответствует делению на c при расчете по модулю m. Аналогично, любой отрицательный показатель степени может быть введен в расчет по модулю m.
(1) теңдігін қанағаттандыратын саны ның модулі бойынша инверсиясы деп аталады және түрінде белгіленеді. Инверсия үшін мұндай белгілеу табиғи болып табылады, себебі, енді біз (1)-ді түрінде жаза аламыз. Яғни – көбейту модуль бойынша есептеуде ға бөлуге сәйкес келеді. Осыған ұқсас, модуль бойынша есептеуде кез келген теріс дәрежені енгізуге болады. .


Мысалы 3. , поэтому 4 является обратным числу 3 по модулю 11.
.
номер можно узнать двумя способами:
,

При расчете вторым методом мы использовали равенство . На самом деле .

указывает на то, что будет Учитывая, что c и m — взаимно простые числа, это равенство

можно записать как И это полностью соответствует (1), только здесь переменные надо обозначить по-другому. Это связано с тем, что для вычисления c^(-1) mod m, т. е. для нахождения числа d, для решения уравнения (2) следует использовать только обобщенный алгоритм Евклида. Обратите внимание, что нас не интересует значение k-переменной, поэтому вторые элементы строк U,V,T можно опустить. При этом, если d-число отрицательное, то к нему следует добавить m-число, поскольку по определению число a mod m берется из множества {0,1,..,m-1 }.

Что мы получаем, и , т.е., .