Решение для коэффициентов

Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из m переменных x₁, x₂, ..., x_m, найти массив m коэффициентов, u_l, u₂, ..., u_m, таких что

u_l * x₁+...+ u_m * x_m, = 1

Малая теорема Ферма

Если m - простое число, и a не кратно m, то малая теорема Ферма утверждает

a^m^-1 ? 1 (mod m)

(Пьер де Ферма (Pierre de Fermat), французский математик, жил с 1601 по 1665 год. Эта теорема не имеет ничего общего с его знаменитой теоремой.)

Функция Эйлера

Существует другой способ вычислить обратное значение по модулю n, но его не всегда возможно использовать. Приведенным множеством остатков mod n называется подмножество полного множества остатков, члены которого взаимно просты с n. Например, приведенное множество остатков mod 12 - это {1, 5, 7, 11}. Если n - простое число, то приведенное множество остатков mod n - это множество всех чисел от 1 до n-1. Для любого n, не равного 1,число 0 никогда не входит в приведенное множество остатков.

Функция Эйлера, которую также называют функцией фи Эйлера и записывают как f(n), - это количество элементов в приведенном множестве остатков по модулю n. Иными словами, f(n) - это количество положительных целых чисел, меньших n и взаимно простых с n (для любого n, большего 1). (Леонард Эйлер (Leonhard Euler), швейцарский математик, жил с 1707 по 1783 год.)

Если n - простое число, то f(n) = n-1. Если n = pq, где p и q -простые числа, то f(n)= (p - 1)(q - 1). Эти числа появляются в некоторых алгоритмах с открытыми ключами, и вот почему. В соответствии с обобщением Эйлера малой теоремы Ферма, если НОД(a,n) = 1, то

a^f⁽ⁿ⁾ mod n = 1

Теперь легко вычислить a^-1 mod n:

x = a^f⁽ⁿ^)-1 mod n

Например, какое число является обратным для 5 по модулю 7? Так как 7 - простое число, f(7) = 7 - 1 = 6. Итак, число, обратное к 5 по модулю 7, равно

5^6-1 mod 7 = 5⁵ mod 7 = 3

Эти методы вычисления обратных значений можно расширить для более общей проблемы нахождения x (если НОД(a,n) = 1):

(a*x) mod n = b

Используя обобщение Эйлера, решаем

x = (b* a^f⁽ⁿ^)-1 ) mod n

Используя алгоритм Эвклида, находим

x = (b* (a^-1 mod n) ) mod n

В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем обобщение Эйлера, особенно для чисел длиной порядка 500 бит. Если НОД(a,n) ? 1, не все потеряно. В этом общем случае (a*x) mod n=b, может иметь или несколько решений, или ни одного.