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

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

*u1 = 1; *u2 = 0; *u3 = *u; tl = *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

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

Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из m переменных x1, x2, xm, найти массив m коэффициентов, м1, и2, Mm, таких что

Ul x1+...+ Um1

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

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

am-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 никогда не входит в приведенное множество остатков.

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

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

a*(n) mod n = 1

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

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

56-1 mod 7 = 55 mod 7 = 3

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

(a*x) mod n = b

Используя обобщение Эйлера, решаем x = (b* a-1 ) mod n Используя алгоритм Эвклида, находим x = (b* (a-1 mod n) ) mod n

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

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

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

В общем случае, если разложение числа n на простые сомножители представляет собой *p2*...*/?t, то система уравнений

(x mod p) = a,-, где i = 1, 2, . . . , t

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

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

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

x = a (mod p), и x = b (mod q)

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

u*q = 1 (mod p)

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

x = (((a - b) *u) mod p) * q + b

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

/* r - это количество элементов в массивах m and u; m - это массив (попарно взаимно простых) модулей u - это массив коэффициентов

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

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

int Chinese remainder (size t r, int *m, int *u) {

size t i;

int modulus;

modulus=1;

for (i=0; i<r;

modulus*=m[i];

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

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

return n;

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

a = x (mod p), и b = x (mod q)

Если a >b mod p, то

x = (((a - (b mod p)) * u) mod p) * q + b

Если a < b mod p, то

x = (((a + p - (b modp))*u) mod p)*q + b

Квадратичные вычеты

Если p - простое число, и a больше 0, но меньше p, то a представляет собой квадратичный вычет по модулю p, если

x2 = a (mod p), для некоторых x