Символ Якоби, ](а,п), представляет собой обобщение символа Лежандра на составные модули, он определ я-ется для любого целого а и любого нечетного целого п. Функция удобна при проверке на простоту. Символ Якоби является функцией на множестве полученных вычетов делителей п и может быть вычислен по различным формулам [1412]. Вот один из способов:
Определение 1: J(a,n) определен, только если п нечетно.
Определение 2: J(0,h) = 0.
Определение 3: Если п - простое число, то символ Якоби ](а,п) = 0, если а делится на п.
Определение 4: Если п - простое число, то символ Якоби ](а,п) = 1, если а - квадратичный вычет по модулю п.
Определение 5: Если п - простое число, то символ Якоби ](а,п) = -1, если а не является квадратичным вычетом по модулю п.
Определение 6: Если п - составное число, то символ Якоби а,п) = J(a,Pl)* ... * J(a,pm), где ри ... , рт - это разложение п на простые сомножители.
Следующий алгоритм рекурсивно рассчитывает символ Якоби:
Правило 1: J(1,h) = 1
Правило 2: ](а*Ь,п) = ](а,п)* ](Ь,п)
Правило 3: J(2,n) =, если (й2-1) /8 нечетно, и -1 в противном случае
Правило 4: ](а,п)= Ща mod n),n)
Правило 5: J(a, bx*b2) = J(a, ij)* J(a, й2)
Правило 6: Если наибольший общий делитель а и Ъ = 1, а также аий нечетны:
Правило 6а: J(a,Z>)= J(ft, а), если (а - 1)(й - 1)/4 четно
Правило 6b: J(a,b)= -](b, а), если (а - 1)(й - 1)/4 нечетно
Вот алгоритм на языке С:
/* Этот алгоритм рекурсивно вычисляет символ Якоби */ 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-1)/2 % 2 == 0)
return jacobi(-a,b); else
return -jacobi(-a,b); if (a % 2 == 0) /* а четно */
if (((b*b -1)/8) % 2 == 0)
return +jacobi(a/2,b); else
return -jacobi(a/2,b); /* по правилам З и 2 */ g = gcd(a,b);
assert(odd(a)); /* это обеспечивается проверкой (а % 2 == 0) */ if (g == a) /* b делится на а */
return 0; /* по правилу 5 */ else if (g != 1)
return jacobi(g,b)*jacobi(a/g,b); /* по правилу 2 */ else if (((a-1)*(b-1)/4) % 2 == 0)
return +jacobi(b,a); /* по правилу 6а */ else
return -jacobi(b,a); /* по правилу 6b */ }
Если заранее известно, что п - простое число, вместо использования предыдущего алгоритма просто вычислите а((й-1)/2) mod п, в этом случае J(a,n) эквивалентен символу Л ежандра.
Символ Якоби нельзя использовать для определения того, является ли а квадратичным вычетом по модулю
и (если, конечно, п не является простым числом). Обратите внимание, что если J( а,п) = 1 ии - составное число, то утверждение, что а является квадратичным вычетом по модулю п, не обязательно будет истиной. Например:
J(7,143) = J(7,ll)* J(7,13) = (-1)(-1) = 1
Однако не существует таких целых чисел х, что х2 = 7 (mod 143).