Необходимо найти элемент B
, обратный элементу A
по модулю C
.
Такой, что (A*B)%C = 1
.
Как найти B
в общем виде?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуНеобходимо найти элемент B
, обратный элементу A
по модулю C
.
Такой, что (A*B)%C = 1
.
Как найти B
в общем виде?
Смотрите.
Для начала, A
и C
должны быть взаимно просты. Если они не взаимно просты, то любая линейная комбинация (A * X) % C = A * X + C * Y
не будет равна единице, то есть, ответа нет.
Окей, пускай числа A
и C
взаимно просты. Для установления этого вы должны использовать алгоритм Евклида для вычисления НОД. Если вы при этом воспользуетесь расширенным алгоритмом Евклида, вы получите не просто НОД, а и те коэффициенты alpha
, beta
, при которых
alpha * A + beta * C = НОД(A, C) = 1.
При этом alpha
и есть ваш ответ, так как
(alpha * A) % C = (1 - beta * C) % C = 1.
Все остальные значения B
получаются из данного прибавлением кратного числу C
.
Есть два пути для решения этой задачи.
Алгоритм Евклида ищет НОД двух чисел. Расширенный алгоритм Евклида одновременно с этим представляет НОД как целочисленную линейную комбинацию исходных чисел:
Ka∙a + Kb∙b = (a, b)
Как легко заметить, если A и C не являются взаимно простыми, то решения нет, а если являются - то коэффициент при A и будет искомым обратным элементом (для доказательства можно заменить в формуле выше b на C и взять обе части равенства по модулю C).
Рекурсивный алгоритм довольно прост. На очередном шаге большее из двух чисел (для определенности, a) представляется как c + k∙b
, после чего алгоритм вызывается рекурсивно для (b, c)
:
Ka∙(c + k∙b) + Kb∙b = (a, b)
Ka∙c + (Kb + Ka∙k)∙b = (c + k∙b, b) = (c, b)
Kc1∙c + Kb1∙b = (c, b)
Отсюда имеем Ka = Kc1 и Kb = Kb1 - Kc1∙k
Получаем примерно такой алгоритм:
ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
ЕСЛИ (b == 0) ВЕРНУТЬ (a, 1, 0)
(d, Kb1, Kc1) = НОД(b, a % b);
ВЕРНУТЬ (d, Kc1, Kb1 - ⌊a/b⌋ ∙ Kc1);
Итеративный алгоритм столь же прост в реализации, но сложнее в понимании. Проще всего использовать матрицы. Для начала, следует записать преобразование коэффициентов в матричном виде:
| 0 1 |
(Ka Kb) = (Kb1, Kc1) | |
| 1 -⌊a/b⌋ |
Эти матричные множители можно будет накопить:
|K11 K12| | 0 1 | |K11` K12`|
| | = | | | |
|K21 K22| | 1 -⌊a/b⌋ | |K21` K22`|
Получается следующий алгоритм:
ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
K = (1, 0)(0, 1) // Начинаем с единичной матрицы
ПОКА b > 0
K = (K[1, 0], K[1, 1])(K[0, 0] - ⌊a/b⌋∙K[1, 0], K[0, 1] - ⌊a/b⌋∙K[1, 1])
(a, b) = (b, a % b)
ВЕРНУТЬ (a, (K[0, 0], K[0, 1])
Теперь, когда у нас есть НОД, осталось найти НОД(A, C), проверить что он равен 1 и взять (Ka % C) в качестве искомого обратного числа.
Время работы - порядка log A по основанию φ итераций (это связано с тем, что худший случай для алгоритма Евклида - соседние числа Фибоначчи).
Если число C заранее известно, или есть достаточно времени на подготовку, то можно воспользоваться формулой Эйлера:
A ^ φ(C) = 1 (mod C) для взаимно простых A и C
Поскольку для имеющих нетривиальные общие делители A и C задача решения все равно не имеет - ограничение нам не помешает.
В соответствии с формулой, ответом будет A ^ (φ(C) - 1) % C
. Быстро найти его можно при помощи алгоритма быстрого возведения в степень:
ФУНКЦИЯ СТЕПЕНЬ (a, x, c):
b = 1
ПОКА x > 0:
ЕСЛИ x - НЕЧЕТНОЕ, ТО
x = x - 1
b = (b * a) % c
ИНАЧЕ
x = x / 2
a = (a * a) % c
ВЕРНУТЬ b
Корректность этого алгоритма легко доказывается если заметить что a ^ x * b
- его инвариант.
Разумеется, после получения ответа надо будет проверить что он правильный, если он будет неверным - значит, ответа вовсе не существует (A и C имеют общие делители).
Этот алгоритм будет работать быстрее чем алгоритм Евклида, потому что тут основание логарифма больше, а сами итерации - проще. Но для применения этого алгоритма требуется заранее знать φ(C)
Реализация расширенного алгоритма Евклида на Python.
def M(A,N):
B = 1
C = 0
D = A % N
E = N
while D > 1:
F = E/D
G = C - B*F
H = E - D*F
C = B
E = D
B = G
D = H
return B % N
X = 7
N = 199
Y = M(X,N)
print Y
Y
- искомый обратный элемент для X
в кольце вычетов по модулю N
.
(1+C)/A
(1+N*C)/A
4*4%5=16%5=1
При N=151/4+15/4+15=19
. Проверка:4*19%5=96%5=1