g = y;

while (x > 0) { g = x; x = y % x;

y = g;

return g;

Этот алгоритм можно обобщить для получения НОД массива m чисел:

/* возвращает НОД (gcd) xl, x2...xm */ int multiple gcd (int m, int *x) {

slze t i;

int g;

if (m < 1)

return 0;

g = x [0];

for (i=l; i<m; {

g = gcd(g, x[i]); /* оптимизация, так как для случайных x[i], g==l в 60% случаев: */ if (g == 1) return 1;

return g;

Обратные значения по модулю

Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:

4*x = 1 (mod 7)

Это уравнение эквивалентно обнаружению x и к, таких что 4x = 7к + 1

где x и к - целые числа. Общая задача состоит в нахождении 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

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

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

Ml * x1+...+ Mm * xm, = 1

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

Если 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 = где p и q -простые числа, то Ф(п)= (p - - 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 (если НОД(a,n) = 1):

(a*x) mod n = b

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

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

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

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

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