Это также можно записать как

a-^x (modH)

Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.

В общем случае у уравнения а"¹ = х (mod n) существует единственное решение, если а и п взаимно просты. Если а и п не являются взаимно простыми, то а"¹ = х (mod n) не имеет решений. Если п является простым чис­лом, то любое число от 1 до и -1 взаимно просто ели имеет в точности одно обратное значение по модулю п.

Так, хорошо. А теперь как вы собираетесь искать обратное значение а по модулю и? Существует два пути. Обратное значение а по модулю п можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.

Вот этот алгоритм на языке C++:

#define isEven(x) ((x & 0x01) == 0)

#define isOdd(x) (x& 0x01)

#define swap(x,у) (х^л= у, у^л= х, х^л= у)

void ExtBinEucliddnt *u, int *v, int *ul, int *u2, int *u3) {

// предупреждение: и и v будут переставлены, если u<v int k, tl, t2, t3;

if (*u < *v) swap(*u<,*v);

for (k = 0; isEven(*u) && isEven(*v); ++k) {

*u»=l; *v »1;

}

*ul = 1; *u2 = 0; *u3 = *u; tl = *v; t2 = *u - 1; t3 = *v;

do {

do {

if (isEven(*u3)) {

if (isOdd(*ul) || is0dd(*u2)) {

*ul += *v; *u2 += *u;

} *ul »* 1; *u2 »= 1; *u3 »= 1;

} if (isEven(t3) || *u3 < t3) { swap(*ul,tl); smap(*u2,t2); smap(*u3,t3);

} } while (isEven(*u3)); while (*ul < tl || *u2 < t2) { *ul += *v; *u2 += *u; }

ul -= tl; *u2 -= t2; *u3 -= t3; } while (t3 > 0);

while (*ul >= *v && *u2 >= *u) { *ul>l -= *v; *u2 -= *u;

} *u «= k; *v «= k; *u3 << k; }

main(int argc, char **argv) { int a, b, gcd; if (argc < 3) {

cerr « "как использовать: xeuclid u v" « endl; return -1;

}

int u = atoi(argv[l]); int v = atoi(argv[2]); if (u <= 0 || v <= 0 ) {

cerr « "Аргумент должен быть положителен!" « endl; return -2;

} // предупреждение: u и v будут переставлены если u < v ExtBinEuclidt&u, &v, &a, &b, Sgcd); cout « a «" * " « и « " + (-" « b « ") * " « v « " = " « gcd « endl; if (gcd == 1)

cout « "Обратное значение " « v << " mod " « u « " is: " « u - b « endl; return 0; }

Я не собираюсь доказывать, что это работает, или приводить теоретическое обоснование. Подробности мо яс­но найти в [863] или в любой из приведенных ранее работ по теории чисел.

Алгоритм итеративен и для больших чисел может работать медленно. Кнут показал, что среднее число в ы-

полняемых алгоритмом делений равно: 0.843*log₂(/i)+ 1.47

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

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

щ*х₁+...+ и_т*х_т, = 1

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

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

а^тЛ = 1 (mod m)

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

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

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

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

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

_fl«">mod/.= l

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

х^а^"¹ mod n

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

5⁶"¹ mod 7 = 5⁵ mod 7 = 3

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

(а*х) mod п = Ъ

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

jc = (i*_fl«">¹ ) modn

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

x = (ft* (a-¹ modH) ) modH

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

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

Если известно разложение числа п на простые сомножители, то для решения полной системы уравнений можно воспользоваться Китайской теоремой об остатках. Основной вариант этой теоремы был открыт в первом веке китайским математиком Сун Цзе.

В общем случае, если разложение числа п на простые сомножители представляет собой _Pl*p₂*...*p_t, то сис­тема уравнений

(x mod/;,) = а„ где i = 1, 2,. . . , г

имеет единственное решение, х, меньшее и. (Обратите внимание, что некоторые простые числа могут поя в-ляться несколько раз. Например, р_х может быть равно р₂.) Другими словами, число (меньшее, чем произведение нескольких простых чисел) однозначно определяется своими остатками от деления на эти простые числа.

Например, возьмем простые числа 3 и 5, и 14 в качестве заданного числа. 14 mod 3 = 2, и 14 mod 5 = 4. С у-ществует единственное число, меньшее 3*5 = 15, с такими остатками: 14. Два остатка однозначно определяют число.

Поэтому для произвольного а < р и Ъ < q (где р и q - простые числа), существует единственное число х, меньшее pq, такое что

х = a (mod/;), и х = Ъ (mod q)

Для получения х сначала воспользуемся алгоритмом Эвклида, чтобы найти и, такое что

u*q=\ (mod/;)

Затем вычислим:

х = (((а - й) *и) mod/;) * # + ft

Вот как выглядит Китайская теорема об остатках на языке С:

/* г - это количество элементов в массивах m and u;

m - это массив (попарно взаимно простых) модулей

и - это массив коэффициентов

возвращает значение п, такое что n == u[k]%m[k] (k=0..r-l) и

n < [m[0]*m[l]*...*m[r-l]

*/

/* Получение функции Эйлера (totient) остается упражнением для читателя. */

int Chinese_remainder (size_t r, int *m, int *u) {

size_t i;

int modulus;

int n;

modulus=l;

for (i=0; i<r; ++i)

modulus*=m[i];

n=0;

for (i=0; i<r; ++i) {

n+=u[i] * modexp(modulus/m[i]*totient(m[i]),m[i]);

n %= modulus;

} return n; }

Обращение Китайской теоремы об остатках может быть использовано для решения следующей проблемы: если ри q - простые числа, и р меньше q, то существует единственное х, меньшее, чем pq, такое что

a=x (mod/;),Hb = x (mod q)

Если а >Ъ mod/;, то

х = (((а - (b mod/;)) * и) mod/;) * q + b

Если а < Ъ mod/;, то

х = (((а +р - (b mod p))*u) mod p)*q + b