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

где Q_k-1 – знаменатель предпоследней подходящей дроби разложения a / m в цепную дробь, или теоремой Ферма-Эйлера, которая утверждает, что если НОД(a, m) = 1, то a^{φ (m)} ≡ 1(mod m),

где φ (m) – функция Эйлера.

Следовательно, x ≡ a^{φ (m) -1}(mod m).

Пример 35. Решить сравнение: 143 *x ≡ 1 (mod 8531).

Функция Эйлера равна: φ (m) = φ (8531)= 8531*(1-1/19)*(1-1/449)= 8064.

Отсюда следует, что

x ≡ a^{φ (m) - 1}(mod m) =143⁸⁰⁶³ (mod8531)= 6443(mod 8531).

Проверка: 143 * 6443=921349 = 1(mod 8531). ▲

Но таким способом решение уравнения сравнения ищут редко. Это связано с тем, что при больших m, нахождение функции φ (m) становится достаточно сложной задачей, особенно при неизвестном разложении.

Пример 36. Решить сравнение: 7283 * x ≡ 1(mod 190116)

Имеем

7283 = 190116 * 0 + 7283

190116 = 7283 * 26 + 758

7283 = 758 * 9 + 461

758 = 461*1+297

461 = 297 * 1 + 164

297 = 164 * 1 + 133

164 = 133 * 1 + 31

133 = 31 * 4 + 9

31 = 9 * 3 + 4

9 = 4 * 2 + 1

4 = 1 * 4 + 0

Получаем: k = 10;

Вычисляем x ≡ (-1)⁹ ∙ 42889 (mod 190116)= -42889 (mod190116) =

= 147227(mod 190116);

Проверка (7283 *147227-1)/ 190116 = 5640 ▲

4.8. Система сравнений первой степени

Система сравнений

a₁∙ x ≡ b₁ (mod n₁);

a₂∙ x ≡ b₂ (mod n₂);

∙ ∙ ∙ (4.2)

a_k∙ x ≡ b_n (mod n_g)

сводится к системе вида

x ≡ b₁ (mod n₁);

x ≡ b₂ (mod n₂);

∙ ∙ ∙ (4.3)

x ≡ b_k (mod n_g)

В случае когда модули n₁, n₂,..., n_g попарно взаимно простые, для решения системы (4.3) используется китайская теорема об остатках.

Китайская теорема об остатках

Эта теорема является одним из полезных и часто используемых в криптографии результатов теории чисел. Она утверждает, что любое значение из множества минимальных положительных представителей (Z/N) классов вычетов по модулю N = n₁∙ n₂∙...∙ n_g, где " i, j Î {1, 2,..., g} НОД(n_i, n_j) = 1, может быть представлен в виде набора остатков от деления этого значения на каждый из сомножителей n_i, то есть имеется взаимно однозначное соответствие R «(r₁, r₂,..., r_g), где RÎ Z/N, r₁Î Z/n₁, r₂Î Z/n₂,..., r_gÎ Z/n_g.

(Любое неотрицательное целое число, не превосходящее произведение модулей, можно однозначно восстановить, если известны его вычеты по этим модулям).

Теорема. Пусть n₁, n₂,..., n_g – наборпопарно взаимно простых чисел, N = n₁∙ n₂∙...∙ n_g; числа c₁, c₂,..., c_g, удовлетворяют условиям

c₁N/ n₁ ≡ 1(mod n₁),

c₂N/ n₂ ≡ 1 mod n₂,

...,

c_gN/ n_g ≡ 1 mod n_g.

Тогда решение системы сравнений

x ≡ r₁ mod n₁,

x ≡ r₂ mod n₂,

_...

x ≡ r_g mod n_g.

имеет вид R' ≡ r₁∙ c₁∙ N/ n₁ + r₂∙ c₂∙ N/ n₂ +...+ r_g∙ c_g∙ N/ n_g (mod N).

Минимальное положительное число R из классов вычетов по модулю N, представляющего собой решение системы сравнений, и является тем элементом кольца Z/N, который ставится в соответствие набору значений r₁, r₂,..., r_g. Подобрать необходимые значения c_iN/ n_i ≡ 1 mod n_i достаточно просто. Их можно вычислить по формуле c_i = N/ n_i ((n_i / N) mod n_i). Если дано некоторое RÎ Z/N, то, выполнив деление R на каждое из чисел n_i, определимоднозначно набор остатков, который ставится в соответствие заданному числу R.