Символ Якоби

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

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

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

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

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

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

Определение 6: Если n - составное число, то символ Якоби J(a,n) = J(a,p₁)* ... * J(a,p_m), где p₁, ... , p_m - это разложение n на простые сомножители.

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

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

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

Правило 3: J(2,n) =, если (n²-1) /8 нечетно, и -1 в противном случае

Правило 4: J(a,n)= J((a mod n),n)

Правило 5: J(a, b₁*b₂) = J(a, b₁)* J(a, b₂)

Правило 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 квадратичным вычетом по модулю n (если, конечно, n не является простым числом). Обратите внимание, что если J(a,n) = 1 и n - составное число, то утверждение, что a является квадратичным вычетом по модулю n, не обязательно будет истиной. Например:

J(7,143) = J(7,11)* J(7,13) = (-1)(-1) = 1

Однако не существует таких целых чисел x, что x² ? 7 (mod 143).