Составители:
Например, мультипликативная обратная величина от числа 7 равна 1
⁄ 7, поскольку 7 ⋅ 1 ⁄ 7 = 1.
В модулярной арифметике [22,23] вычисление обратной величины
является более сложной задачей. Например, решение сравнения
4 ⋅ x ≡ 1 (mod 7)
эквивалентно нахождению таких значений x и k , что
4 ⋅ x ≡ 7 ⋅ k + 1,
где x и k – целые числа.
Таким образом, основной
задачей данного алгоритма является
нахождение такого целого числа x, что
a ⋅ x (mod n) = 1 или a
-1
≡ x (mod n).
Решение этой задачи не всегда существует. Например, обратная
величина для числа 5 по модулю 14 равна 3, так как
5 ⋅ 3 = 15 ≡ 1 (mod 14).
В то же время, число 4 не имеет обратной величины по mod 14, так как
числа 4 и 14 не являются взаимно простыми.
Таким образом, сравнение a
-1
≡ x (mod n) имеет единственное
решение, если a и n - взаимно простые числа.
Если числа a и n не являются взаимно простым, то сравнение
a
-1
≡ x (mod n) не имеет решения.
Рассмотрим основные методы нахождения обратных величин.
Пусть целое число a ∈ {0, 1, 2,…, n-1}. Если НОД (a, n) = 1, то
ax
i
(mod n) при x
i
= 0, 1, 2,…, n-1 является перестановкой множества (0,
1, 2,…,n-1).
Например, если a = 3 и n = 7, (НОД (3, 7) = 1), то
3 ⋅ x
i
(mod 7) при x
i
= 0, 1, 2, …,6
является последовательностью 0, 3, 6, 2, 5, 1, 4, то есть перестановкой
множества {0, 1, 2, …, 6}.
Это становится неверным, когда НОД (a, b) ≠ 1. Например, если a = 2
и n = 6, то
2 ⋅x
i
(mod 6) ≡ 0, 2, 4, 0, 2, 4 при x
i
= 0, 1, 2,…, 5.
Если НОД (a, b) = 1, то только тогда существует обратное число a
-1
, 0 <
a
-1
< n, такое что a ⋅ a
-1
≡ 1 (mod n).
Действительно, если a ⋅ x
i
(mod n) является перестановкой чисел 0, 1,
…, n - 1, то существует такое x
i
, что a ⋅x
i
≡ 1 (mod n).
156
Страницы
- « первая
- ‹ предыдущая
- …
- 152
- 153
- 154
- 155
- 156
- …
- следующая ›
- последняя »
