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

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

Роберт Соловей и Фолькер Штрассен разработали алгоритм вероятностного тестирования простоты числа, который использует символ Якоби. Определяет числа как составные или вероятно простые. Распознает числа Кармайкла как составные.
Итак, для начала необходимо ввести нужные понятия.
Квадратичный вычет. Если число 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).

Вычисление символа Якоби

Не получается написать правильную реализацию алгоритма вычисления символа Якоби J(Q/P). Сначала сам алгоритм:

Вход: Q , P — целые числа.

Выход: значение символа Якоби.

1) s = 0, u = Q, v = P.

2) Вычисляем r — наименьший положительный остаток при делении u на v . Вычисляем целое k >= 0 и нечетное t , такие, что r = t * 2^k . Вычисляем `s = s + k * (v^2 — 1)/8 + (t — 1)*(v — 1)/4 (mod 2)

3) Если t = 1 , то символ Якоби равен (-1)^s . Конец.

4) Если t >= 3 , то u = v , v = t , переходим на шаг 2.

Здесь J(-104, 997) должен быть равен -1, а моя реализация выдает 1.

Еще тесты из хелпа 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 .

Дополнение: в тернарном выражении я ошибся. Если s == 1 (true), то надо возвращать -1, потому что показатель степени нечетный.

Основы теории чисел

Определение. Число называется квадратичным вычетом по модулю , если сравнение $x^2 \equiv a (mod \ m)$ имеет решение при некотором целом , если сравнение $x^2 \equiv a (mod \ m)$ не имеет решений, то называют квадратичным невычетом.

1.6.1 Символ Лежандра-Якоби

Определение. Символ Лежандра определяется следующим образом:

$\left(\frac \right)=\left\<\begin<array><rl>0,& \text<если $a$ делится на $p$>;\\1,& \text<если $a$ - квадратичный вычет> Следующие свойства используются для вычисления символа Лежандра: <ol> <li><img decoding=$ .

Решение. Будем выбирать числа случайно, и тестировать их с помощью символа Лежандра.

Пусть выбранное нами случайное число оказалось 51:

$\left(\frac<51><449>\right)=\left[\text<по свойству 3>\right]=\left(\frac<3><449>\right)\left(\frac<17><449>\right)=\left[\text<по свойству 5>\right]=\\<\left(-1\right)>^<\frac<448 \cdot 2><4>>\left(\frac<449><3>\right)<\left(-1\right)>^<\frac<448 \cdot 16><4>>\left(\frac<449><17>\right)=\left[\text<по свойству 2>\right]=\left(\frac<2><3>\right)\left(\frac<7><17>\right).» /> <img decoding=$ и нечетного числа $n= _<1> _<2><\dots> _<k>» />, где числа <img decoding=$ символ Якоби равен символу Лежандра, одинаковое обозначение не введёт нас в заблуждение. Отметим, что символ Якоби не является полным аналогом символа Лежандра, т.е. равенство

$\left(\frac<n>\right)=\left\<\begin<array><rl>0,& \text <если $a$ не взаимно просто с >n;\\1,& \text<если $a$ - квадратичный вычет> в общем случае не выполняется. Свойства символа Якоби: <ol> <li><img decoding=$ , — нечетные числа, то $\left(\dfrac<m><n>\right)=<\left(-1\right)>^<\frac<\left(m-1\right)\left(n-1\right)><4>>\left(\dfrac<n><m>\right).» /></li> </ol> Повторим наши вычисления из примера с помощью символа Якоби: <img decoding=$ — нечетное число, — произвольный квадратичный невычет. Положим c=<z>^<q>» /> и будем искать корень <img decoding= . Поскольку

$<\left(<c>^<2<\alpha >_<1>+4<\alpha >_<2>+<\dots>>\right)>^<<2>^<s-1>>=<z>^<q \cdot <2>^<s>(<\alpha >_<1>+2<\alpha >_<2>+<\dots>)>=<z>^<(p-1)(<\alpha >_<1>+2<\alpha >_<2>+<\dots>)>=1 <img decoding=$ — квадратичный невычет, а $^<\frac<p-1><2>>=1 (mod \ p)» />, так как <img decoding=$ — квадратичный вычет. Поэтому $^<\frac<p-1><4>>» /> есть корень из единицы, и может быть либо 1, либо <img decoding=$ . В первом случае берём $<\alpha >_<0>=0″ />, во втором <img decoding=$ и получим:

$^<\frac<p-1><8>>^<<2>^<s-3>><z>^<\frac<p-1><4><\alpha >_<0>+\frac<p-1><2><\alpha >_<1>>=^<<2>^<s-3>> Аналогично предыдущему, <img decoding=$ . В первом случае берём $<\alpha >_<1>=0″ />, во втором <img decoding=$ , $<x>^<2>=a (mod \ p)» />, мы найдём все коэффициенты <img decoding=$ — простое число, — квадратичный вычет по модулю .

Выход: число такое, что <x>^<2>=a
<ol>
<li>Выбрать произвольный квадратичный невычет <img decoding= .

Вычислить

<c>_<0>=<z>^<q>» />.</li>
<li>Положить <img decoding=

, $<R>_<0>=^<\frac<q+1><2>>» />, <img decoding=$ и перейти к шагу 4.

Отметим, что на каждом шаге числа и _» /> и <img decoding= на шаге 5 нужно последовательно возводить его в степень.

Алгоритм Тонелли-Шенкса не позволяет находить корень по -примарному модулю. Для решения этой задачи нам потребуется следующая идея. Если не делится на , и мы вычислили <x>_<0>» /> — корень из <img decoding= по модулю , то корень <x>_<1>» /> из <img decoding= по модулю ^<n>» /> можно искать в виде <img decoding= , то имеем:

$\frac<<x>_<0>^<2>-a> +2<t>_<1><x>_<0>=0 <img decoding=$

Отметим, что <x>_<1>^<2>=a
(mod 
^<2>)» />, <img decoding=

Продолжая последовательность <x>_» /> по описанному принципу, мы найдём <img decoding= делится на , имеем:

<x>^<2>=<a

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

<x>^<2>=<a

В этом случае два решения $\pm \widetilde<x>» /> находим из уравнения <img decoding=$ . Найдём остальные решения $\pm \widetilde<x>+b» /> из уравнения: <img decoding=$

$\pm 2 ^<2k>\widetilde<x>b+ ^<2k>^<2>=\left(l-r\right) ^<m>.» /> Поскольку <img decoding=$ , то ^<2k>b» /> делится на <img decoding= делится на ^<m-2k>» />. Наоборот, если <img decoding= — кратное числа ^<m-k>» />, и <img decoding= , то $<\left(p\left(\pm \widetilde<x>+b\right)\right)>^<2>=a (mod \ p^<m>)» />. Тогда корнями исходного уравнения будут <img decoding=$ .

Пример 1.37 Найти квадратный корень из по модулю .

Имеем: $<x>^<2>=63 \ mod \ 81″ />. Делим обе части на 9. Тогда: <img decoding=$ по модулю 567 .

Поскольку $567=81 \cdot 7$ , имеем: $<x>^<2>=18 \ mod\ 81″ />, <img decoding=$ (из предыдущего примера) и $x=\pm 3 (mod \ 7)» />. Из полученных двенадцати систем уравнений по китайской теореме об остатках имеем: <div class='yarpp yarpp-related yarpp-related-website yarpp-template-list'>  <div>Похожие публикации:</div><ol> <li><a href=$ Где находится батарея в ноутбуке asus