Составители:
1. Определение обратной величины методом поочерёдной проверки
значений 1, 2,… , n - 1, пока не будет найден
x = a
-1
(mod n) такой, что a ⋅ x ≡ 1 (mod n).
Пример ΙΙΙ [11]: дано n = 7, a = 5.
Необходимо найти x = a
-1
(mod n).
a ⋅ x ≡ 1(mod n) или 5 ⋅ x ≡ 1(mod 7).
Получаем x = 5
-1
(mod 7) = 3.
2. Определение a
-1
(mod n) ≡ a
ϕ(n)-1
(mod n) (если известна функция
Эйлера ϕ(n)), используя алгоритм быстрого возведения в степень.
Таблица П.1
Модуль n
Функция ϕ(n)
n - простое n - 1
n
2
n(n – 1)
. . . . . .
n
r
n
r-1
(n – 1)
p ⋅ q (p, q – простые)
(p –1)(q –1)
. . . . . .
p
i
еi
(- простые) p
i
е
i-1
(p
i
– 1)
Пример ΙV [11]: дано n = 7, a = 5. Найти x = a
-1
(mod n) =5
-1
(mod 7).
Модуль n = 7 – простое число. Поэтому функция Эйлера
ϕ(n) = ϕ(7) = n – 1 = 6. Обратная величина от 5 по mod 7
a
-1
(mod n) = a
ϕ(n)-1
(mod n) =
= 5
6-1
mod 7 = 5
5
mod 7 = (5
2
mod 7)(5
3
mod 7) mod 7 =
= (25 mod 7)(125 mod 7) mod 7 = (4 ⋅ 6) mod 7 = 24 mod 7 = 3.
Итак, x = 5
-1
(mod 7) = 3.
3. Определение обратной величины a
-1
(mod n) с помощью
расширенного алгоритма Евклида (РАЕ). РАЕ при заданных
неотрицательных целых числах a и b позволяет вычислить целые
числа u
1
, u
2
и u
3
такие, что a ⋅ u
1
+ b ⋅ u
2
= u
3
= НОД (a, b).
В процессе вычисления используются вспомогательные векторы (v
1
,
v
2
, v
3
), (t
1
, t
2
, t
3
). Действия с векторами производятся таким образом, что в
течение всего процесса вычисления выполняются соотношения
158
Страницы
- « первая
- ‹ предыдущая
- …
- 154
- 155
- 156
- 157
- 158
- …
- следующая ›
- последняя »
