Page 24 - 4395

 INVOLUTION — піднесення до степеня за модулем.
Далі описано вказані функції і головний модуль програми.
Функція INVERSE (див. В.2) реалізує розширений алгоритм
Евкліда [1, c. 58-60]. SCRIPT-файл для цього алгоритму наведений у

додатку В. У програмі цей SCRIPT-файл перетворений на функцію.
Центральною тут є вбудована функція MatLab

[G,C,D] = gcd(A,B), A, B > 0,

яка повертає найбільший спільний дільник G, а також цілі

коефіцієнти C і D, таки що

А.*С + В.*D = G.

Якщо G = 1, то це рівняння є діофантовим, отже добутки А*С
та В*D дорівнюють одиниці за певним модулем, тобто є взаємно
оберненими:

А*С = - В*D + 1;

B*D = - A*C + 1.

Останнє і означає, що

А*С mod B = 1;
B*D mod A = 1;
або
-1
A mod B = C mod B;
-1
B mod A = D mod A.

Для наших цілей достатньо повертати лише дві величини
(рядок 7), а саме

[G,C] = gcd(Z,E),

де Z - вхідне число, Е - значення модуля.

Після перевірки умови G = 1 за допомогою оператора IF (рядок
8) обернене до Z за модулем Е знаходиться за формулою (рядок 9)
invZ=mod(C,E). Якщо умова G = 1 не виконується, виводиться

повідомлення: “Z i E – не взаємно прості числа!” (рядок 11), після
чого оператор KEYBOARD передає управління до клавіатури. У
цьому режимі доступні всі модулі програми і всі засоби MatLab, що
дозволяє виправити помилки. Для повернення у програму, що

виконується, необхідно ввести команду RETURN. При цьому робота
програми починається з оператора, наступного після KEYBOARD.
Функція INVOLUTION призначена для піднесення цілого

числа до степеня за модулем.

24