Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
4*x = 1 (mod 7)
Это уравнение эквивалентно обнаружению x и k, таких что
4x = 7k + 1
где x и k - целые числа. Общая задача состоит в нахождении x, такого что
1 = (a*x) mod n
Это также можно записать как
a-1 ? x (mod n)
Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.
В общем случае у уравнения a-1 ? x (mod n) существует единственное решение, если a и n взаимно просты. Если a и n не являются взаимно простыми, то a-1 ? x (mod n) не имеет решений. Если n является простым числом, то любое число от 1 до n -1 взаимно просто с n и имеет в точности одно обратное значение по модулю n.
Так, хорошо. А теперь как вы собираетесь искать обратное значение a по модулю n? Существует два пути. Обратное значение a по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.
Вот этот алгоритм на языке C++:
#define isEven(x) ((x & 0x01) == 0)
#define isOdd(x) (x& 0x01)
#define swap(x,y) (x^= y, y^= x, x^= y)
void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3) {
// предупреждение: u и v будут переставлены, если u<v
int k, tl, t2, t3;
if (*u < *v) swap(*u<,*v);
for (k = 0; isEven(*u) && isEven(*v); ++k) {
*u>>=1; *v >>1;
}
*u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u - 1; t3 = *v;
do {
do {
if (isEven(*u3)) {
if (isOdd(*ul) || isOdd(*u2)) {
*u1 += *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" << end1;
return -1;
}
int u = atoi(argv[1]);
int v = atoi(argv[2]);
if (u <= 0 || v <= 0 ) {
cerr << "Аргумент должен быть положителен!" << end1;
return -2;
}
// предупреждение: u и v будут переставлены если u < v
ExtBinEuclid(&u, &v, &a, &b, &gcd);
cout << a <<" * " << u << " + (-"
<< b << ") * " << v << " = " << gcd << end1;
if (gcd == 1)
cout << "Обратное значение " << v << " mod " << u << " is: "
<< u - b << end1;
return 0;
}
Я не собираюсь доказывать, что это работает, или приводить теоретическое обоснование. Подробности можно найти в [863] или в любой из приведенных ранее работ по теории чисел.
Алгоритм итеративен и для больших чисел может работать медленно. Кнут показал, что среднее число выполняемых алгоритмом делений равно:
0.843*log2(n) + 1.47