(x mod Pi) = 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;

int n;

modulus=1;

for (i=0; i<r;

modulus*=m[i];

n=0;

for (i=0; i<r; {

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

Не все значения a соответствуют этому требованию. Чтобы a было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей n. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:

12 = 1 = 1 (mod 7)

22 = 4 = 4 (mod 7)

32 = 9 = 2 (mod 7)

42 = 16 = 2 (mod 7)

52 = 25 = 4 (mod 7)

62 = 36 = 1 (mod 7)

Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений x, удовлетворяющих любому из следующих уравнений, не существует:

x2 = 3 (mod 7)

x2 = 5 (mod 7)

x2 = 6 (mod 7)

Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.

Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p - 1)/2 квадратичных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю p. Кроме того, если a - это квадратичный вычет по модулю p, то у a в точности два квадратных корня, один между 0 и (p-1)/2, а второй - между (p - 1)/2 и (p - 1). Один из этих квадратных корней одновременно является квадрати ч-ным остатком по модулю p, он называется плавным квадратным корнем.

Если n является произведением двух простых чисел, p и q, то существует ровно (p - l)(q - 1)/4 квадратичных вычетов по модулю n. Квадратичный вычет по модулю n является совершенным квадратом по модулю n, потому что для того, чтобы быть квадратом по модулю n, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и 30. У каждого квадратичного вычета ровно четыре квадратных корня.

Символ Лежандра

Символ Лежандра, L(a,/;), определен, если a - это любое целое число, а p - простое число, большее, чем 2. Он равен 0, 1 или -1.

L(a,/7) = 0, если a делится на p.

L(a,/7) = 1, если a - квадратичный вычет по модулю

L(a,/7) = -1, если a не является квадратичным вычетом по модулю

L(a,p) можно рассчитать следующим образом:

L(a,/;) = a-1)/2 mod p

Или можно воспользоваться следующим алгоритмом:

1. Если a = 1, то L(a,p) = 1

2. Если a четно, то L( a,/;) = L(a/2,/;) * "2-1)/8

3. Если a нечетно (и 1), то L(a,/;)= L(p mod a, ,)*(-l)(a-1)(p-1)/4

Обратите внимание, что этот метод также является эффективным способом определить, является ли a квадратичным вычетом по модулю p (для простого числа p).

Символ Якоби

Символ Якоби, J(a,n), представляет собой обобщение символа Лежандра на составные модули, он определ я-ется для любого целого a и любого нечетного целого n. Функция удобна при проверке на простоту. Символ Яко-би является функцией на множестве полученных вычетов делителей n и может быть вычислен по различным формулам [1412]. Вот один из способов:

Определение 1: J( a,n) определен, только если n нечетно.

Определение 2: J(0, n) = 0.

0пределение 3: Если n - простое число, то символ Якоби J(a,n) = 0, если a делится на n.

0пределение 4: Если n - простое число, то символ Якоби J( a,n) = 1, если a - квадратичный вычет по модулю

0пределение 5: Если n - простое число, то символ Якоби J( a,n) = -1, если a не является квадратичным вычетом по модулю n.

0пределение 6: Если n - составное число, то символ Якоби J(a,n) = J(a,/71)* ... * J(a,/7m), где p1, ... , pm - это разложение n на простые сомножители.

Следующий алгоритм рекурсивно рассчитывает символ Якоби:

Правило 1: J(1,n) = 1

Правило 2: J(a*b,n) = J(a,n)* J(b,n)

Правило 3: J(2,n) =, если (n2-1) /8 нечетно, и -1 в противном случае Правило 4: J(a,n)= J((a mod n),n) Правило 5: J(a, b1*b2) = J(a, b1)* J(a, bz)

Правило 6: Если наибольший общий делитель a и b = 1, а также a и b нечетны: Правило 6a: J(a,b)= J(b, a), если (a - l)(b - 1)/4 четно Правило 6b: J(a,b)= -J(b, a), если (a - l)(b - 1)/4 нечетно Вот алгоритм на языке C:

/* Этот алгоритм рекурсивно вычисляет символ Якоби */ int jacobi(int a, int b) { int g;

assert(odd(b));

if (a >= b) a %= b; /* по правилу 4 */ if (a == 0) return 0; /* по определению 1 */ if (a == 1) return 1; /* по правилу 1 */ if (a < 0)

if ((b-l)/2 % 2 == 0)

return jacobi(-a,b);

else

return -jacobi(-a,b); if (a % 2 == 0) /* a четно */

if (((b*b -1)/8) % 2 == 0)

return +jacobi(a/2,b);

else

return -jacobi(a/2,b); /* по правилам 3 и 2 */

g = gcd(a,b);

assert(odd(a)); /* это обеспечивается проверкой (a % 2 == 0) */ if (g == a) /* b делится на a */

return 0; /* по правилу 5 */

else if (g != 1)

return jacobi(g,b)*jacobi(a/g,b); /* по правилу 2 */

else if (((a-l)*(b-l)/4) % 2 == 0)

return +jacobi(b,a); /* по правилу 6a */

else

return -jacobi(b,a); /* по правилу 6b */

Если заранее известно, что n - простое число, вместо использования предыдущего алгоритма просто вычи с-лите a((n-1)/2) mod n, в этом случае J(a,n) эквивалентен символу Лежандра.

Символ Якоби нельзя использовать для определения того, является ли a квадратичным вычетом по модулю