Символ Якоби

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

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

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

х² = a (mod/;), для некоторых х

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

I² = 1 = 1 (mod 7)

2² = 4 = 4 (mod 7)

3² = 9 = 2 (mod 7)

4² = 16=2 (mod 7)

5² = 25=4 (mod 7)

6² = 36 = 1 (mod 7)

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

х² = 3 (mod 7)

х² = 5 (mod 7)

х² = 6 (mod 7)

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

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

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

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

Ца,р) = 0, если а делится на р.

Ца,р) = 1, если а - квадратичный вычет по модулю р.

Ца,р) = -1, если а не является квадратичным вычетом по модулю р.

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

Ца,р) = ^"^1)/2 mod p

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

1. Еслиа= 1,тоЦа,/>) = 1

2. Если а четно, то Ца,р) = Ца/2,р) * (-I)**²-¹''⁸

3. Если а нечетно (и Ф 1), то Ца,р)= Up mod а, р)*(-1)^^'⁴

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

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

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

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

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

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

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

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

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

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

Правило 2: ](а*Ь,п) = ](а,п)* ](Ь,п)

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

Правило 4: ](а,п)= Ща mod n),n)

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

Правило 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

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