Как вычислить символ якоби

,

где—символы Лежандра[Виноградов,1953], т.е. ариф­­метические функции чиселaир_i , опре­де­ленные для прос­­тых нечетныхр_iи целыха, не де­лящихся наP, при­­чем= 1, если срав­не­ниеx 2 º a(mod p_i) раз­ре­ши­­мо, а в про­­тив­ном случае= -1. Часто символ Ле­­­жанд­ра, а сле­д­­о­ва­тельно, и символ Якоби, который яв­ля­ется его обоб­щением, доопределяют для чиселa, де­ля­­щих­­ся наp_i(для символа Якоби соответственно наP), по­­лагая, что в этом случае= 0. Символ Яко­би об­ладает свой­ст­ва­ми, ана­ло­гич­ны­ми свойствам сим­во­ла Ле­жанд­ра, а имен­но:

если a ºb (modP), то=;

= 1;

;

=.;

,

где P, Q— по­­ло­­­жи­тель­ные нечетные взаимно простые чис­ла (квад­­­ра­тич­ный закон взаимности, который впервые до­ка­зан для сим­во­ла Лежандра Гауссом в 1876 г.);

;

.

Перечисленные свойства позволяют легко вы­чис­­­лять символ Якоби, не прибегая к решению срав­­­­не­ний. За­­ме­тим, что при фиксирован­ном P сим­вол Яко­би является дей­ствительным ха­рак­­­тером муль­ти­пли­ка­тив­­ной группы клас­сов вы­­че­­тов по мо­ду­лю P.

Процедура syjac, построенная по алгоритму, учи­­­ты­ва­­­ющему приведенные свойства, вы­чис­­­­ляет зна­че­­ние сим­во­ла Якобипо квадра­тич­­­­ному за­ко­ну вза­­имности. При этом полагает­ся сле­­дующее (таб­л. 1.4):

Значение сим­во­ла Якоби .

P — не­­чет­ное

P — простое и a является квад­­ра­тич­ным невычетом числа m

Если a и P име­ют не­три­ви­аль­ный общий множитель

Формальные параметры процедуры. Входные:a, p(тип integer).Выходной:r(типinteger) — зна­че­ние сим­во­ла Якоби.

Как вычислить символ якоби

Еще тесты из хелпа Maple: jacobi(12, 3) = 0 , jacobi(28, 21) = 0 , jacobi(6, 11) = -1 , jacobi(226, 135) = 1 , jacobi(26, 35) = -1 , jacobi(-286, 4272943) = 1 , jacobi(888, 1999) = -1 .

Определение. Число называется квадратичным вычетом по модулю , если сравнение имеет решение при некотором целом , если сравнение не имеет решений, то называют квадратичным невычетом.

— нечетные числа, то — произвольный квадратичный невычет. Положим — квадратичный вычет по модулю .

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

Продолжая последовательность , имеем:

и делится на . Следовательно, решение есть тогда и только тогда, когда делится на четную степень , поэтому далее можем писать:

В этом случае два решения по модулю .

Имеем: .

Поскольку , имеем:

Алгоритм Соловея-Штрассена

Роберт Соловей и Фолькер Штрассен разработали алгоритм вероятностного тестирования простоты числа, который использует символ Якоби. Определяет числа как составные или вероятно простые. Распознает числа Кармайкла как составные.
Итак, для начала необходимо ввести нужные понятия.
Квадратичный вычет. Если число p — простое и 0 < a < p, то число a является квадратичным вычетом по модулю p, если существуют значения x такие, что
x2 = a (mod p).
Для того, чтобы число a было квадратичным вычетом по модулю n, оно должно быть квадратичным вычетом по модулю всех простых делителей n. Например, если n = 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 = 1 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. Если n — произведение двух простых чисел p и q, то существует ровно (p – 1)(q – 1)/4 квадратичных вычетов по модулю n.
Связь между простыми числами и квадратичными вычетами устанавливается с помощью символов Лежандра и Якоби.
Символ Лежандра, который обозначается как L(a, p) — это функция, определенная, если a — любое целое число, а p — простое число, превышающее 2. Символ Лежандра может принимать значения 0, 1 и –1.
L(a, p) = 0, если a делится на p.
L(a, p) = 1, если a — квадратичный вычет по модулю p,
L(a, p) = –1, если a — квадратичный невычет по модулю p.
Сжато, эти факты записываются так:
L(a, p) = a^((p – 1)/2) mod p.

Алгоритм вычисления символа Лежандра.

1. Если a = 1, то L(a, p) = 1.
2. Если число a четное, то L(a, p) = L(a/2, p)*((-1)^((p^2-1)/8)).
3. Если число a — нечетное и a != 1, то L(a, p) = L(p mod a, a)*((–1)^((a–1)*(p–1)/4)).
Символ Якоби, который обозначается как J(a, n) — это обощение символа Лежандра на составные модули. Это функция, определенная для всех целых чисел a и нечетных целых чисел n. Символ Якоби может принимать значения 0, 1 и –1.
Символ Якоби можно задать следующим образом.
1. Символ Якоби определен только для нечетных чисел n.
2. J(0, n) = 0.
3. Если n – простое число, то J(0, n) = 0, если a делится на n.
4. Если n – простое число, то J(0, n) = 1, если a — квадратичный вычет по модулю n.
5. Если n – простое число, то J(0, n) = –1, если a — квадратичный невычет по модулю n.
6. Если n – составное число, то J(a, n) = J(a, p1)*. *J(a, pm), где p1. pm — разложение n на простые множители.

Алгоритм вычисления символа Якоби.

1. J(1, n) = 1.
2. J(a*b, n) = J(a, n)*J(b, n).
3. J(2, n) = 1, если (n^2 – 1)/8 является четным, и –1 в противном случае.
4. J(a, n) = J((a mod m), n).
5. J(a, b1*b2) = J(a, b1)J(a, b2).
6. Если gcd(a, b) = 1 и, кроме того, числа a и b являются нечетными, то
6.1. J(a, b) = J(b, a), если (a – 1)*(b – 1)/4 является четным числом.
6.2. J(a, b) = –J(b, a), если (a – 1)*(b – 1)/4 является нечетным числом.
Если n — простое число, то символ Якоби эквивалентен символу Лежандра.
Символ Якоби нельзя использовать для проверки, является ли число a квадратичным вычетом по модулю n (кроме случая, когда число n — простое). Если J(a, n) = 1 и n — составное число, то число a не всегда является квадратичным вычетом:
J(7, 143) = J(7, 11) * J(7, 13) = (–1)*(–1) = 1,
хотя не существует целых чисел x таких, что x2  7 (mod 143).